↩ 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.

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.

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.

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. 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 eleven 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.