Binary search pitfalls: midpoint overflow and off-by-one boundaries

What it is

Binary search finds a position in sorted data by repeatedly halving the candidate range. Three bugs recur. First, midpoint overflow: the cited Google Research post describes how (low + high) / 2 fails in the JDK's binarySearch once the sum exceeds the maximum int, and gives low + ((high - low) / 2) or (low + high) >>> 1 as fixes. Second, boundary convention: whether high is inclusive or exclusive dictates the loop condition and the updates; mixing conventions produces infinite loops or a skipped element. Third, duplicates: Python's bisect documents bisect_left (insertion point before equal entries) and bisect_right (after), which is the difference between "first match" and "position after the last match". Go's sort.Search avoids most of this by asking for the smallest index in [0, n) at which a monotone predicate becomes true.

Why it matters

The routine appears in pagination cursors, time-series lookups, version-range checks, git bisect-style searches over builds and many "find the first that fails" tasks. A wrong boundary is silent: results are off by one only for some inputs, typically the first or last element.

How to apply

• Prefer the library function (bisect, sort.Search, Arrays.binarySearch); write your own only when the predicate is not an array lookup.
• Use the predicate form: find the first index where pred(i) is true, requiring pred to be false then true across the range. Lower bound, upper bound and "first failing version" are all instances.
• Use a half-open interval: lo, hi = 0, n; while lo < hi: mid = lo + (hi - lo) // 2; if pred(mid): hi = mid else lo = mid + 1; return lo. The + 1 on the else branch guarantees progress.
• Test the edges: empty input, one element, target below the first and above the last, all elements equal, target at index 0 and n-1.
• Verify the data is sorted under the same comparison used for searching (bisect with key= must match the sort key).

Pitfalls

Python integers do not overflow, but the boundary bugs remain. A search over floats breaks in the presence of NaN, because comparisons stop being an ordering. Data sorted with locale collation and searched bytewise is not sorted for the search. bisect_left returns an insertion point for absent values, not -1: check i < len(a) and a[i] == x. Binary search on a linked list is linear because indexing is.