Binary search
easyDoubling the array size costs exactly one more step. A million elements need 20 comparisons; a billion need 30. Includes the overflow bug that sat in the JDK for nine years.
O(1)Average O(log n)Worst O(log n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How binary search works
The guessing game where every answer is 'higher' or 'lower'. Because the array is sorted, comparing the target against the middle element settles an entire half in one step: 18 candidates become 9, then 4, then 2, then 1. Doubling the input adds exactly one comparison - a million elements need 20, a billion need 30.
This module implements the classic inclusive variant: lo = 0, hi = n - 1, loop while lo <= hi, and a three-way branch on a[mid] - return on equality, lo = mid + 1 when a[mid] is too small, hi = mid - 1 when it is too large. The invariant is the proof of correctness: the target, if present, is always inside a[lo..hi], so when lo passes hi it was never there.
The midpoint is computed as lo + (hi - lo) / 2, never (lo + hi) / 2. The obvious form overflows once lo + hi exceeds the integer maximum - a bug that sat undetected in the JDK's binary search for nine years and in Programming Pearls for twenty. The safe form costs nothing extra and cannot overflow.
Step by step
- Search for 63 in the 18-element sorted array [3, 8, 12, ..., 97]. lo = 0, hi = 17: every index is a live candidate.
- mid = 0 + (17 - 0) / 2 = 8. a[8] = 47 < 63, so indices 0..8 are all too small - lo becomes 9. Nine candidates left.
- mid = 13. a[13] = 74 > 63, so indices 13..17 are all too large - hi becomes 12. Four candidates remain.
- mid = 10. a[10] = 58 is still below 63, so lo becomes 11 - two candidates remain, a[11..12].
- mid = 11. a[11] = 63 equals the target: found at index 11 in 4 comparisons. A linear scan would have used 12.
- Had 63 been absent, lo would eventually pass hi, the empty range would prove absence, and -1 comes back - with lo naming the insertion point.
Complexity
| Best case time | O(1) |
|---|---|
| Average time | O(log n) |
| Worst case time | O(log n) |
| Space | O(1) |
Each step discards half the remaining candidates.
Reference implementation
Python
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids overflow in fixed-width ints
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1JavaScript
function binarySearch(a, target) {
let lo = 0, hi = a.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1); // avoids overflow
if (a[mid] === target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Java
static int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // NOT (lo + hi) / 2 - that overflows
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}C++
int binarySearch(const vector<int>& a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // NOT (lo + hi) / 2 - that overflows
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Worth noticing
Every step throws away half of what is left
Watch the range shrink: 18 candidates, 9, 4, 2, 1. That is why doubling the array size costs exactly one more step. A million elements need 20 comparisons; a billion need 30.
`lo + (hi - lo) / 2`, not `(lo + hi) / 2`
The obvious midpoint overflows once lo + hi exceeds the integer maximum. This bug sat undetected in the JDK's binary search for nine years, and in Programming Pearls for twenty. The form used here cannot overflow.
The invariant is what makes it correct
At every step the target, if present, is inside a[lo..hi]. Each branch preserves that. When lo passes hi the range is empty, so the target was never there - which is exactly the proof of correctness.
Sorted input is not optional
Type an unsorted array: it gets sorted first here on purpose. Given genuinely unsorted data, binary search does not search slowly - it silently returns the wrong answer.
Common pitfalls
- (lo + hi) / 2 overflows in fixed-width integers once the array is large enough - the nine-year JDK bug. Always write lo + (hi - lo) / 2.
- Mixing boundary conventions: pairing hi = n - 1 with while lo < hi skips the last element, and pairing hi = n with this loop reads a[n] out of bounds.
- Writing lo = mid or hi = mid in this inclusive variant - on a two-element range mid equals lo, the range stops shrinking, and the loop never terminates.
- Feeding it unsorted data. It does not crash or slow down - it silently returns a wrong answer, which is far worse. This visualizer sorts your input first for exactly that reason.
- Searching under a different ordering than the array was sorted by - a comparator mismatch, like JavaScript's default lexicographic sort putting 10 before 9, breaks the halving logic invisibly.
Where it is used
- The standard library: Java's Arrays.binarySearch, C++ std::binary_search, and the engine inside Python's bisect module.
- Key lookup inside each node of a B-tree - the index structure under most relational databases.
- The building block here: lower and upper bound, exponential search, and binary search on the answer all embed it.
- Interview staples built directly on it - search in rotated sorted array, find peak element, search a 2D sorted matrix.
Frequently asked questions
What is the time and space complexity of binary search?
Average and worst case O(log n), because each step discards half of the remaining candidates; best case O(1) when the first midpoint hits the target. The iterative version here uses O(1) space - two indices and a midpoint, no recursion stack.
Why write lo + (hi - lo) / 2 instead of (lo + hi) / 2?
In fixed-width arithmetic lo + hi can exceed the integer maximum and wrap negative, producing a garbage midpoint. This exact bug hid in the JDK's binary search for nine years and in Programming Pearls for twenty. lo + (hi - lo) / 2 never forms a sum larger than hi, so it cannot overflow.
Does binary search work on an unsorted array?
No - and it fails silently rather than loudly. The halving step assumes everything left of a too-small midpoint is also too small, which only sorted order guarantees. On unsorted input it returns a wrong index, or -1 for an element that is present. Sort first, or use linear search.
What does binary search return when the target is missing?
This variant returns -1 once lo passes hi, because an empty range proves the target was never present. Usefully, lo finishes at the exact index where the target would be inserted to keep the array sorted - which is what the lower bound variant returns directly.