Templates

Binary Search

We are searching for x in our search space.

Left most search

The termination condition is important. At some point we will find x, At that point eventually left == right. We can return any of left or right.

while left < right:
    mid = left + (right - left) // 2
    if helper(mid) < x:
        left = mid + 1
    else:
        right = mid
return left