Binary Search, Really Understood
The template that avoids off-by-one bugs, why the midpoint is written (lo + hi) >>> 1, and how to find boundaries, not just exact matches.
On this page
Binary search is deceptively hard. The idea - halve a sorted search space each step - is trivial, but the implementation is a minefield of off-by-one errors, and its real power is finding boundaries, not just exact matches. Getting truly comfortable with it unlocks a surprising number of problems.
The template that doesn't break
The reliable form uses inclusive bounds [lo, hi] and a carefully written midpoint:
// find target in a sorted array, or -1 — O(log n)
int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) { // inclusive: loop while the range is non-empty
int mid = lo + (hi - lo) / 2; // avoids integer overflow of (lo + hi)
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1; // search the right half
else hi = mid - 1; // search the left half
}
return -1;
}Two details that prevent bugs: write the midpoint as lo + (hi - lo) / 2 (or (lo + hi) >>> 1) so a
huge lo + hi can't overflow an int; and always move lo or hi past mid (mid + 1,
mid - 1) so the range strictly shrinks and the loop can't spin forever.
Finding boundaries, not just matches
The more powerful use is finding the leftmost or rightmost position satisfying a condition - the
first element ≥ target, the insertion point, the boundary between "false" and "true." This is what Java's
Arrays.binarySearch insertion point and problems like "first bad version" need:
// leftmost index where a[i] >= target (lower bound)
int lowerBound(int[] a, int target) {
int lo = 0, hi = a.length; // note: hi = length, exclusive
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1; // mid too small → go right
else hi = mid; // mid could be the answer → keep it in range
}
return lo; // first index with a[i] >= target
}The shift is subtle but important: instead of "did I find it?", you ask "is mid on the correct side
of the boundary?" and narrow toward the edge. Master this and "find the first/last position where…"
problems become routine.
The overflow and infinite-loop traps
Two classic bugs: writing mid = (lo + hi) / 2 can overflow when lo + hi exceeds Integer.MAX_VALUE
(famously a bug that lived in Java's own library for years) - use lo + (hi - lo) / 2. And failing to
move a bound past mid can loop forever when the range stops shrinking. Decide your bound convention
(inclusive vs. exclusive) up front and be consistent.
The number-guessing game is binary search. You guess 50; 'higher' eliminates 1-50 in one move; you guess 75; 'lower' eliminates 76-100. Each guess halves what's left, so you corner any number in about seven guesses instead of a hundred. The boundary version is a subtly different game: instead of 'is it exactly this?', you ask 'is the answer at least this?' and keep narrowing to the exact tipping point where 'no' becomes 'yes' - which is how you find a first or last position, not just an exact value.
A sorted array has been rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2]). Find a target in O(log n). Explain how you can still binary-search when the array isn't fully sorted.
Why write the binary-search midpoint as lo + (hi - lo) / 2 instead of (lo + hi) / 2?
Key takeaways
- Binary search halves a sorted search space each step - O(log n) - but is bug-prone; use a consistent template.
- Write the midpoint as lo + (hi - lo) / 2 (or (lo + hi) >>> 1) to avoid integer overflow.
- Always move lo or hi past mid so the range strictly shrinks, preventing infinite loops.
- The powerful use is finding boundaries (first >= target, insertion point), asking 'is mid on the right side?' rather than 'is it a match?'.
- It extends beyond plain sorted arrays - e.g. a rotated sorted array, where one half is always sorted.