Binary Search Visualizer

Binary search finds a value in a million-element sorted array in at most twenty comparisons. Not twenty thousand — twenty. That is the practical meaning of logarithmic time, and no other elementary algorithm demonstrates it so starkly.

It is also famously difficult to write correctly. Jon Bentley reported that around ninety per cent of professional programmers failed to produce a correct implementation when given a couple of hours, and the version in Java's standard library shipped with an integer overflow bug that survived undetected for nine years. Twelve lines of code, and almost every one of them has a trap.

What is binary search?

Binary search operates on a sorted collection. It examines the middle element of the current range. If that element is the target, it is done. If the target is larger, everything from the middle leftwards can be discarded; if smaller, everything from the middle rightwards goes. Either way, half the remaining candidates disappear from a single comparison.

The sorted precondition is not a suggestion. Run binary search on unsorted data and it will not merely be slow — it will confidently return the wrong answer, reporting that a value which is present is absent. This is worse than an error, because nothing fails loudly.

The power comes from the ratio of information to work. A linear scan's comparison eliminates one candidate. A binary search's comparison eliminates half of everything remaining. Doubling the array size adds exactly one comparison to the worst case.

Why it works

The invariant is: if the target is present, it lies within `A[lo..hi]`. It is true initially with the full range. Each iteration examines the midpoint and, because the array is sorted, can eliminate one side with certainty — if A[mid] < target then every element at or left of mid is also smaller, so none can be the target.

The range shrinks by at least half each iteration. Starting from n candidates, after k iterations at most n/2^k remain, so the loop terminates after at most ⌈log₂(n+1)⌉ iterations. When lo > hi the range is empty, and by the invariant the target is not present anywhere.

That is the whole proof, and it makes clear why sorted order is load-bearing: the elimination step depends entirely on being able to infer the relationship of every element on one side from a single comparison with the midpoint.

Step-by-step walkthrough

Search [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] for 23. Ten elements, so at most four comparisons.

1. Range is 0–9. Midpoint is index 4, holding 16. 23 > 16, so discard indices 0–4. Five candidates eliminated by one comparison.
2. Range is 5–9. Midpoint is index 7, holding 56. 23 < 56, so discard indices 7–9.
3. Range is 5–6. Midpoint is index 5, holding 23. Match — return index 5.
4. Three comparisons. A linear search would have needed six.

What binary search is really for

Finding an exact value in an array is the textbook use and the least interesting one. The technique generalises far beyond it, and this generalisation is what interviewers are usually probing for.

Boundary finding. lowerBound returns the first position where a value could be inserted while keeping the array sorted, and upperBound the last. Together they give you the range of all occurrences of a value in O(log n), which is how you count duplicates without scanning. These are the variants you will actually use — bisect_left and bisect_right in Python, lower_bound and upper_bound in C++.

Binary search on the answer. When a problem asks for the minimum or maximum value satisfying some monotone condition, you can binary-search the *answer space* rather than an array. 'What is the smallest ship capacity that lets us deliver all packages in D days?' has no array to search, but the predicate 'can we do it with capacity c' is monotone — false for small c, true for large — so you can binary-search over c. This pattern shows up constantly in competitive programming and in real capacity-planning problems.

Searching a rotated array, finding a peak element, and locating the crossover point in a monotone function are all the same idea: any predicate that is false-then-true over a range can be binary-searched, whether or not there is an array involved.

How the animation above works

The highlighted band shows the range still under consideration; struck-through cells have been eliminated. What is worth watching is the size of the eliminated group after each single comparison — roughly half of whatever was left, every time.

Set the array size to 32 and count the comparisons: five at most, because 2⁵ = 32. Then note what happens when you search for a value that is not present — the range shrinks to nothing and the algorithm concludes absence in the same logarithmic number of steps. Unlike linear search, an unsuccessful binary search costs no more than a successful one.

The visualiser sorts the array before searching, because binary search on unsorted input would silently return wrong answers, and demonstrating that would teach the wrong lesson.

Time complexity

Best case O(1) — the target is at the first midpoint examined.

Average and worst case O(log n). Precisely, at most ⌈log₂(n+1)⌉ comparisons. For 1,000 elements that is 10; for a million, 20; for a billion, 30. Each doubling of the data adds exactly one comparison, which is why logarithmic algorithms scale so comfortably.

The one caveat is that this assumes O(1) random access. On a linked list, reaching the midpoint costs O(n) traversal, so binary search degenerates to O(n log n) — worse than simply scanning. This is why sorted linked lists use skip lists or balanced trees instead.

It is also worth being honest about the constant factor: below roughly a hundred elements, linear search is often faster in wall-clock time despite doing more comparisons, because its sequential access is cache-friendly and its branches are predictable. Binary search's midpoint comparison is close to a coin flip, which modern CPUs mispredict about half the time.

Space and variants

O(1) auxiliary space for the iterative form, which is what you should write. The recursive version is O(log n) stack for no benefit — it is naturally tail-recursive, and the loop is no harder to read.

Lower bound finds the first element not less than the target; upper bound finds the first strictly greater. Both always run the full log n iterations rather than exiting early on a match, and both are more useful than plain binary search because they answer insertion and range questions as well as membership.

Exponential search doubles an index until it overshoots the target, then binary-searches the bracketed range. It runs in O(log i) where i is the target's position, which beats O(log n) when the target is near the front, and it works on unbounded or infinite sorted sequences where n is not known.

Interpolation search guesses the position proportionally rather than always taking the midpoint, like looking up 'Zebra' near the back of a dictionary. On uniformly distributed data it averages O(log log n), but it degrades to O(n) on skewed data — a real risk that makes it a specialist tool.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Binary Search in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Iterative binary search on a sorted array. Returns the index, or -1.
 *
 * Two details carry all the risk: the overflow-safe midpoint, and the +1/-1
 * when narrowing (without them the range can stop shrinking and loop forever).
 */
function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1; // lo is now the index where target would be inserted
}

const data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(data, 23)); // 5
console.log(binarySearch(data, 24)); // -1

Advantages and disadvantages

Real-world applications

• Standard library lookups — Arrays.binarySearch, std::lower_bound, Python's bisect module.
• Database B-tree indexes, which binary-search within each node to decide where to descend.
• Version control bisection: git bisect is binary search over commit history, finding the commit that introduced a bug in log₂n builds.
• Capacity and threshold problems — the minimum machine size, rate limit or deadline satisfying a monotone constraint — searched over the answer space rather than an array.
• Finding insertion points to maintain sorted collections, and counting occurrences of a value via the bound variants.
• Numerical root finding by bisection, which is the same halving idea applied to a continuous function.
• Autocomplete and prefix lookups over sorted dictionaries, where lower and upper bound together isolate the matching range.

Interview questions

The questions that actually get asked about Binary Search, with the answers an interviewer is listening for.

1. Q1. Why is the midpoint computed as lo + (hi - lo) / 2?

   Because (lo + hi) / 2 overflows when the sum exceeds the maximum integer, producing a negative index and an out-of-bounds access. Since hi ≥ lo, the difference hi - lo is always non-negative and no larger than hi, so the safe form can never overflow. This exact bug existed in Java's Arrays.binarySearch for nine years.

2. Q2. How do you find the first and last occurrence of a repeated value?

   Use lower bound and upper bound. Lower bound finds the first index whose value is not less than the target; upper bound finds the first strictly greater. The difference between them is the number of occurrences, and both run in O(log n). The key change from plain binary search is that neither stops on a match — they keep narrowing to find the boundary.

3. Q3. What is 'binary search on the answer'?

   Applying binary search to a range of candidate answers rather than to an array. It works whenever a predicate is monotone — false up to some threshold, then true forever after. For example, to find the minimum ship capacity that delivers all packages within D days, you binary-search the capacity and evaluate feasibility at each midpoint. There is no array involved; the search space is the answer domain itself.

4. Q4. How would you binary-search a rotated sorted array?

   At each step, at least one half of the current range is still properly sorted — compare arr[lo] with arr[mid] to determine which. If the target lies within that sorted half's value range, recurse there; otherwise recurse into the other half. It remains O(log n), because you still eliminate half the range per comparison.

5. Q5. Why is binary search sometimes slower than linear search?

   On small arrays, cache behaviour and branch prediction dominate the comparison count. Linear search walks contiguous memory that the prefetcher loads ahead of time, and its loop branch is highly predictable. Binary search jumps to distant midpoints — often a cache miss each time — and its comparison outcome is close to a coin flip, which CPUs mispredict roughly half the time. Below about a hundred elements the scan usually wins.

Common mistakes

• Computing the midpoint as (lo + hi) / 2, which overflows on large indices in fixed-width integer languages.
• Writing lo = mid or hi = mid instead of mid + 1 and mid - 1 in the standard form, which stops the range shrinking and loops forever.
• Mixing inclusive and exclusive bounds — hi = length with while (lo <= hi) reads past the end; hi = length - 1 with while (lo < hi) misses the last element.
• Running it on unsorted data, which returns a confidently wrong answer rather than an error.
• Returning the first match found when the first or last *occurrence* of a duplicated value was wanted — plain binary search may land anywhere in a run of equal values.
• Using the recursive form and paying O(log n) stack for an algorithm that is naturally a loop.
• Forgetting that the terminal value of lo is the correct insertion point, and recomputing it with a second pass.

Optimisation tips

• Write the iterative version. It is O(1) space, no harder to read, and eliminates a class of stack-related failure modes.
• Prefer lower bound and upper bound over plain binary search — they handle duplicates, insertion points and range counts, and they are no more complex.
• Fall back to a linear scan once the range drops below roughly 32–64 elements; the cache and branch-prediction advantages outweigh the extra comparisons.
• Use exponential search when the target is likely near the front, or when the collection has no known length — it costs O(log i) rather than O(log n).
• Consider a branchless implementation with conditional moves for hot paths; it eliminates the mispredictions that dominate binary search's real cost.
• If insertions are frequent, do not maintain a sorted array at all — a hash map gives O(1) average lookup, and a balanced tree gives O(log n) insert and search together.

Summary

Binary search halves a sorted range on every comparison, finding any element in at most ⌈log₂(n+1)⌉ steps — twenty for a million elements. It needs sorted data and O(1) random access, and it returns silently wrong answers if the first condition is violated.

The exact-match version is the least useful form. Lower bound and upper bound handle duplicates, insertion points and range counts in the same time, and 'binary search on the answer' generalises the technique to any monotone predicate, with no array involved at all. Write it iteratively, use lo + (hi - lo) / 2 for the midpoint, and in production call your standard library's version, which is already correct.

Frequently asked questions

Related algorithms

• Linear Search

  Check every element in order until the target turns up — no assumptions required.

  O(n)Beginner

• Merge Sort

  Split the array down to single elements, then merge sorted halves back together.

  O(n log n)Intermediate

• Quick Sort

  Partition around a pivot so everything smaller lands left and larger lands right.

  O(n log n)Intermediate