Binary Search: Keep Discarding Half

Binary search finds a target in sorted data. It examines the middle of the current range and uses whether the target is greater or smaller to reduce the next range by half.

The important part is not merely looking at the middle. Because the data is in ascending order, no value smaller than the middle can be on its right, and no larger value can be on its left. That fact justifies discarding one side without examining it.

Use the same data as the visualization: 20 values from 5 through 100 in steps of 5. low and high mark the two ends of the range where the answer may still exist.

The first comparison shows that 55 is greater than 50, so ten values at or below 50 are removed at once. Next, values from 75 upward are removed, then values from 60 upward. The remaining value, 55, matches.

Every step preserves this condition: if the target exists in the array, it lies between low and high. This is a loop invariant. Showing that each range update preserves it is the basis for arguing that the algorithm is correct.

Linear search may need n comparisons for n candidates. Binary search changes the candidate count from n to n/2, n/4, n/8, and so on with each comparison.

Twenty values take at most five comparisons, about one million take at most 20, and about one billion take at most 30. The value of discarding half grows with the data set.

The O(log n) running time assumes a structure such as an array where the middle element can be accessed immediately. A linked list takes time to walk to the middle, so reducing the number of comparisons alone does not give the same total speed.

In the basic implementation, both low and high belong to the search range. Compare the middle only while a range remains, expressed as low <= high.

Move right with low = mid + 1 and left with high = mid - 1. mid has already been compared, so it must leave the candidate range. Forgetting +1 or -1 can select the same middle forever and prevent termination.

This version returns any one matching element. When duplicate values exist, finding the first or last matching position requires a boundary-search variant that continues left or right after a match.

Binary search is not limited to locating a value. If a decision is false up to some point and true from then onward, binary search can find the first true position. This property is called monotonicity.

If predicate(mid) is true, the answer is mid or somewhere to its left. If it is false, the answer lies to the right. Either decision still discards half the candidates.

The first product price over a budget, the fewest servers that meet capacity, or the shortest duration that satisfies a condition can all be understood as searches for a minimum successful value or maximum failing value.

Now consider a classic interview puzzle. It initially looks exactly like binary search, but an additional constraint changes which algorithm is best.

As the floor rises, the result changes exactly once from survives to breaks, so the predicate is monotonic. Does that mean we should start at floor 50 and keep halving?

The optimal strategy first drops an egg at floor 14. If it survives, go 13 floors higher to 27, then 12 higher to 39, reducing the interval by one each time. When it breaks, use the second egg one floor at a time above the last safe floor.

Suppose the worst case allows d drops. If the first egg breaks on drop one, the second can check d-1 remaining floors; if it breaks on drop two, the second can check d-2. The most floors covered are therefore d + (d-1) + ... + 1. Thirteen drops cover only 91 floors, while 14 cover 105. A worst case of 14 for 100 floors is both achievable and minimal.