Binary search, and getting the boundary right

Sorted input is information#

If an array is sorted, looking at one element tells you something about everything on both sides of it. Compare the middle element with your target and one half of the array is eliminated. Repeat and the search space halves every step, which is why 200000 elements take at most 18 comparisons.

low = 0, high = n - 1
while low <= high:
    mid = low + (high - low) / 2
    if a[mid] == target: return mid
    if a[mid] < target: low = mid + 1
    else: high = mid - 1

Use low + (high - low) / 2 rather than (low + high) / 2. The second one can overflow a 32 bit integer when both ends are large, and that is a bug that only appears on the big test cases.

The part people get wrong#

Finding an element that exists is straightforward. Almost every real question is the harder version: where would it go if it is not there?

Look at the loop above when the target is missing. It ends with low > high, and at that moment low is exactly the index where the target belongs. Everything before low is smaller than the target, and everything from low onwards is larger. That is the insert position, and it comes out of the loop for free.

That is worth remembering as a fact about the algorithm: when the loop finishes without a hit, low is the answer to "where does this go".

Getting the invariant right#

The reason binary search is easy to write wrong is that there are several correct versions with different conventions. Pick one and keep it:

• while low <= high with high = n - 1 treats high as a valid index, and narrows by one on each side.
• while low < high with high = n treats high as one past the end, and never moves high past mid.

Mixing the two gives you either an infinite loop or a missed element. Write down what low and high mean before the loop, and check that every branch keeps it true.

Where this shows up#

Anything monotonic can be binary searched, not only arrays. If you can ask a yes or no question whose answer flips exactly once as some number increases, you can binary search the number itself: the smallest capacity that finishes in time, the smallest speed that works, the largest value that still fits. The array is the special case where the question is "is a[i] at least the target".

Common mistakes#

• Returning -1 when the question asked for an insert position.
• Computing the midpoint in a way that overflows.
• Moving a boundary to mid instead of mid + 1 or mid - 1, which stalls the loop forever.