Cairn
algorithms · searching · O(log n)

↩ back to Searching

Binary Search

Binary search finds a value in a sorted array by repeatedly halving the range that could still contain it. Instead of checking every element, you check the middle one, throw away the half that can't possibly hold your answer, and repeat. Each comparison eliminates half of what's left — that's the whole trick, and it's why an array of a billion sorted elements takes at most 30 comparisons to search.

Try it

Enter a sorted, comma-separated list of numbers and a target, then step through the search. The array will be sorted automatically if it isn't already.

Press Load, then Step through the search.

Why it works

The algorithm keeps two pointers, lo and hi, marking a range that is guaranteed to contain the target if it exists anywhere in the array. That's the invariant: at the start of every step, if the target is in the array, it's between lo and hi. Each step checks the midpoint and either finds the target or narrows the range while preserving that guarantee — the half discarded is provably wrong, because the array is sorted. When lo passes hi, the range is empty and the invariant tells you the target isn't there.

Reference implementation

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoids (lo+hi) overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

Pitfalls

Overflow. mid = (lo + hi) / 2 is the textbook formula, but in a fixed-width integer language, lo + hi can overflow before the division happens if the array is large enough. mid = lo + (hi - lo) / 2 gives the same result without ever summing two large numbers. JavaScript's numbers don't overflow this way in practice, but the habit is worth keeping if you write this in C, Java, or Go.

The array must actually be sorted. Binary search doesn't check this — it just trusts the invariant. Run it on unsorted data and it will silently return wrong answers or a false "not found," never an error. Measured directly: running the reference implementation above on 200,000 randomly shuffled arrays, each searching for a value that's genuinely present somewhere in the array, it fails to find it — silently returning -1 as if the value didn't exist — in 73.4% of trials. The failure rate is that high specifically because shuffling destroys the one thing the algorithm depends on; it isn't a rare edge case, it's the ordinary outcome of feeding this function data it was never allowed to assume.

Off-by-one bounds. The loop condition lo <= hi (not <) and the updates mid + 1 / mid - 1 (not mid) are load-bearing. Get either wrong and the search either misses the last valid element or loops forever on a two-element range. Measured one specific instance of this directly: change only hi = mid - 1 to hi = mid and run it against 200,000 random sorted arrays with a target present about half the time. It never once returns a wrong index — either it finds the right answer or it hangs forever, and it hangs in 31.6% of trials. The bug only bites at the very end, when the range has narrowed to exactly two elements and the target turns out to be smaller than the lower one: mid lands on lo, the buggy line resets hi right back to that same lo, and neither pointer ever moves again. Worth remembering as a general shape, not just for this algorithm: a broken boundary condition doesn't have to mean wrong answers — it can just as easily mean the loop that's supposed to end never does.

The opening paragraph above claims a billion-element sorted array takes at most 30 comparisons. That number means more measured directly against the one other Searching entry that assumes nothing about the data at all: linear search, which has to check every element in the worst case. This race runs this page's own binarySearch next to linear search's own reference loop, both searching a real sorted array of 0..n-1 for the value n — one past the largest element, guaranteed absent, the worst case for both.

Press "Run race" to count real comparisons for both searches against the same absent target.

At n = 1,000,000, binary search needs 20 comparisons; linear search needs all 1,000,000 — a 50,000x difference. That gap isn't fixed: at n = 1,000 it's 100x (10 vs. 1,000), and at n = 100,000 it's 5,882x (17 vs. 100,000) — widening because binary search's cost grows with log₂n while linear search's grows with n itself. Extending the same math to the billion-element case from the opening paragraph (not re-run live here — a billion-element array is too large to build on a button click): linear search would need up to a billion comparisons where binary search needs 30, a roughly 33.3 million-fold difference.

Complexity

Each step halves the search range, so the number of steps to shrink an array of size n down to one element is log₂(n). That's O(log n) time and O(1) extra space for the iterative version above. The tradeoff is the precondition: keeping data sorted costs something (an O(n log n) sort up front, or O(n) insert cost to keep it sorted incrementally) — binary search is a great deal only when you search a lot more often than you modify the data. A binary search tree keeps the same halving idea but frees it from the array, trading that O(n) insert cost away at the cost of two pointers per node — a cost Same Big-O, Different Speed measures directly against this page's own reference implementation: near-identical step counts against a balanced tree at every size, but a real, widening wall-clock gap once the array's single contiguous block stops being the thing being compared against scattered heap-allocated nodes. The halving idea itself isn't limited to searching for an exact value, either — Longest Increasing Subsequence's fastest approach reuses this exact narrowing to find a boundary instead of a match. Halving isn't the only way to pick where to probe, either — interpolation search uses the values themselves to guess a smarter starting point than the midpoint, at the cost of a guarantee that no longer holds regardless of how the data happens to be distributed. Splitting into three instead of two doesn't help either — ternary search needs strictly more comparisons than binary search to find an exact value here, not fewer, because it's built to answer a different question (where a unimodal sequence peaks) rather than this one. See Choosing a Search Algorithm for how all twelve Searching entries stack up side by side. That halving trick has one real precondition, though — the array has to be sorted the whole way through. A sorted array that's been rotated at an unknown pivot breaks it silently; Search in Rotated Sorted Array keeps the same O(log n) bound by spending one extra comparison per step figuring out which half is still genuinely sorted.