Binäre Suche, wirklich verstanden
Die Vorlage, die Off-by-One-Fehler vermeidet, warum der Mittelpunkt als (lo + hi) >>> 1 geschrieben wird und wie man Grenzen findet, nicht nur exakte Treffer.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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.