First True: Predicate Binary Search
Search a monotonic yes/no boundary.
Search a Yes/No Boundary
Many problems hide a monotonic predicate: false, false, then true forever. Binary search can find that first true without a sorted array.
# FFFFTTTT -> find first TWhat Monotonic Means
A predicate is monotonic when once it turns true it stays true. That single property is what lets you binary-search the boundary.
def ok(x):
return x * x >= targetAll lessons in this course
- Classic Binary Search Without Bugs
- bisect_left and bisect_right
- First True: Predicate Binary Search
- Binary Search on the Answer