Given a sorted array, binary search finds a target in time. The algorithm is simple — repeatedly check the middle, narrow to half — but its off-by-one boundary cases are infamous for being miswritten.
The canonical template
``` lo = 0 hi = n - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if A[mid] == target: return mid elif A[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 ```
Note `mid = lo + (hi - lo) // 2`, not `(lo + hi) // 2` — the former avoids integer overflow on very large arrays (real-world bug in Java's binary search until 2006).
Lower bound and upper bound
Often you don't want the index of an exact match — you want the smallest index whose value is target (lower bound), or the smallest whose value is target (upper bound). These return insertion points. Template:
``` lo = 0, hi = n while lo < hi: mid = lo + (hi - lo) // 2 if A[mid] < target: lo = mid + 1 else: hi = mid return lo ```
This always converges and returns a valid insertion point in .
Binary search on the answer
When the input isn't an array but a problem with a monotone yes/no property over an answer space, binary-search the answer. Examples: "minimum capacity that can ship within D days," "smallest divisor that keeps the sum under T." If you can write a feasibility check "is feasible?" and feasibility is monotone in , binary search finds the boundary in .
Rotated sorted array
A sorted array rotated at some pivot. Binary search still works in : at each step, exactly one of the two halves is sorted; check whether the target lies inside it; recurse into that half if so, into the other half otherwise.
When binary search fails silently
The data must actually be sorted, and your monotone predicate must really be monotone. Search with a slightly broken predicate often "works" on the test cases you tried but loops or returns wrong answers on edge cases. Always check vs at the boundaries.