Binary Search

What is it?

If you search a list one item at a time, finding a value in a million-item list could take up to a million checks. But if the list is sorted, there's a much faster way: check the middle item. If it's too big, the answer must be in the left half; if it's too small, it must be in the right half. Repeating this — always looking at the middle of whatever's left — is called binary search, and it can find a value in a million-item list in about 20 checks instead of a million.

Explain like I'm 10

It's how you'd find a word in a paper dictionary: you don't start at page 1. You open to the middle, see you've gone too far or not far enough, and jump to the middle of the correct half — repeating until you land on the word.

Examples

Binary search implementation

function binarySearch(sortedArray, target) {
  let low = 0;
  let high = sortedArray.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (sortedArray[mid] === target) return mid;
    if (sortedArray[mid] < target) {
      low = mid + 1; // search the right half
    } else {
      high = mid - 1; // search the left half
    }
  }

  return -1; // not found
}

How it works

Each check eliminates half of the remaining possibilities. Starting with n items, after one check there are n/2 left to consider, then n/4, then n/8 — this halving is what makes binary search take only about log2(n) steps, dramatically fewer than checking every item.

[1,3,5,7,9,11,13] — looking for 11
        ↓ check middle (7) → too small → search right half
   [9,11,13]
        ↓ check middle (11) → found!

Why does it exist?

Binary search is one of the clearest demonstrations of why algorithm choice matters: the same problem, solved with a smarter approach on sorted data, goes from O(n) to O(log n) — a difference that becomes enormous as data grows.

When to use it

Reach for binary search whenever you're repeatedly searching a large, sorted collection — it turns an O(n) scan into an O(log n) lookup, which matters a lot once the data gets big.

When not to use it

If your data isn't sorted and can't easily be kept sorted, binary search doesn't apply — sorting it first costs more than a single linear search would. And for a very small list, the overhead of tracking low/high/mid isn't worth it over just checking each item.

Common mistakes

• Using binary search on data that isn't sorted — it silently gives wrong answers instead of erroring.

• Getting the low/high update backwards, causing an infinite loop or skipped elements.

• Off-by-one errors in the midpoint calculation or the boundary updates.

Practice exercises

1. Easy:

   Implement binary search for a sorted array of numbers, returning the index of a target value.

2. Medium:

   Modify binary search to return the index where a value should be inserted to keep the array sorted, even if it isn't found.

3. Hard:

   Use binary search to find the smallest number in a sorted array that has been rotated (e.g. [4,5,6,1,2,3]).

Interview questions

What is required for binary search to work?

The data must be sorted — binary search relies on being able to rule out half the remaining data based on a single comparison.

What is the time complexity of binary search?

O(log n), since each step cuts the remaining search space in half.

Why is O(log n) so much better than O(n) for large inputs?

Because logarithmic growth is extremely slow — doubling the input only adds one more step, whereas linear growth doubles the work.

Walk through why binary search takes O(log n) steps: starting with n items, how many remain after each comparison?

Each comparison eliminates one whole half of the remaining range, so after 1 step there are about n/2 items left, after 2 steps n/4, after k steps n/2^k. The search ends once that shrinks to about 1 item — n/2^k ≈ 1 — which means k ≈ log₂(n), so the number of steps grows logarithmically with n, not linearly.

What precondition does binary search require that makes it inapplicable to a linked list, even though a linked list can be sorted?

Binary search needs O(1) random access to jump straight to an arbitrary index — the middle of the current range. A linked list only supports sequential access — reaching the middle element requires walking from the head, O(n) — so 'jumping to the middle' costs as much as scanning the whole thing, eliminating the benefit binary search is supposed to provide.

In `const mid = Math.floor((low + high) / 2)`, why does this implementation need `while (low <= high)` rather than `while (low < high)`?

With low <= high, the loop still checks the case where low === high — the single remaining candidate element — before concluding the target isn't present. Using low < high instead would skip checking that last remaining element, incorrectly reporting 'not found' for a target that's actually the very last candidate.

What's the classic overflow bug with `mid = Math.floor((low + high) / 2)` in languages with fixed-width integers, and how do implementations avoid it?

If low and high are both large enough that their sum exceeds the maximum representable integer (32-bit signed overflow in Java/C++), low + high wraps to a negative or garbage value before the division happens, producing a nonsensical mid. The fix is mid = low + Math.floor((high - low) / 2), which never sums the two directly. This specific overflow isn't a practical concern for ordinary array indices in JavaScript, since its numbers are IEEE-754 doubles representing integers exactly up to 2^53 — far beyond any realistic array length — but it's a real trap in fixed-width-integer languages.

How would you modify binary search to find the leftmost (first) occurrence of a target value that appears multiple times in a sorted array?

Instead of returning immediately on arr[mid] === target, record mid as a candidate answer and keep searching the left half (high = mid - 1) to see if an earlier occurrence exists, narrowing until low > high. The last recorded candidate is the leftmost occurrence — still O(log n), since it's one binary search with a modified 'found' branch.

Symmetrically, how would you find the rightmost (last) occurrence of a duplicated target?

On arr[mid] === target, record mid as a candidate and keep searching the right half (low = mid + 1) instead of stopping, to see whether a later occurrence exists. The last recorded candidate once low > high is the rightmost occurrence.

How would you find the index where a value should be inserted into a sorted array to keep it sorted, even if that exact value isn't present?

Run a binary search that narrows low/high as usual, but instead of returning -1 on failure, return low once the loop ends — at that point low has converged to exactly the first index whose value is >= the target, which is the correct insertion point to keep the array sorted.

How would you search for a target in a sorted array that's been rotated at an unknown pivot (e.g. `[4,5,6,7,0,1,2]`), while keeping O(log n) time?

At each step, compare arr[low] to arr[mid] to determine which half is the 'normally sorted' one. If arr[low] <= arr[mid], the left half is sorted, so check whether the target falls within that sorted range — search there if it does, otherwise search the right half. If the right half is the sorted one instead, apply the symmetric logic. Either way, one comparison still discards half the remaining elements each step, preserving O(log n).

In the rotated-array search, why does at least one half always have to be properly sorted, no matter where the pivot is?

Rotating a sorted array creates exactly one 'break point' where a smaller value follows a larger one. Any contiguous range that doesn't straddle that break point is still in ascending order. Splitting at mid means the break point can only fall within one of the two halves (or neither), so the other half is guaranteed fully sorted, giving a reliable way to decide where to search next.

For a rotated sorted array that may contain duplicate values (e.g. `[3,3,1,3]`), why can the 'which half is sorted' check fail, and what does that do to worst-case time complexity?

If arr[low] === arr[mid] === arr[high], duplicates make it impossible to tell from that comparison alone which half is properly ordered. The standard fix is to shrink the range conservatively by one element (low++ or high--) and try again, rather than eliminating a full half. In the worst case (an array of nearly all-identical values), this degrades the algorithm to O(n), since it may only discard one element at a time instead of half the range.

How would you find the minimum element in a rotated sorted array (no duplicates) using binary search?

Compare arr[mid] to arr[high]. If arr[mid] > arr[high], the minimum must be to the right of mid (the rotation point is in the right half), so set low = mid + 1. Otherwise, the minimum is at mid or to its left, so set high = mid (not mid - 1, since mid itself could be the answer). This still converges in O(log n) since the search range keeps halving.

You have a fully sorted 2D matrix where every row is sorted left-to-right and the first element of each row is greater than the last element of the previous row. How would you binary search it in O(log(m·n))?

Treat the matrix as if flattened into one array of length mn without copying it — for a candidate flat index i, map it back to `(row, col) = (Math.floor(i / cols), i % cols)`, compare `matrix[row][col]` to the target, and narrow `low`/`high` exactly like a normal 1D binary search. Since the total element count is mn, the number of steps is O(log(mn)).

A different, more common kind of sorted 2D matrix has every row sorted left-to-right *and* every column sorted top-to-bottom, but rows aren't necessarily continuous with each other. Why doesn't the flattened-1D binary search work here, and what O(m+n) approach does?

Without the 'each row continues where the previous left off' guarantee, mapping a flat index to (row, col) no longer corresponds to a globally sorted sequence, so binary search's halving logic breaks. Instead, start at the top-right corner: move left if the current value is bigger than the target (eliminating that column), move down if smaller (eliminating that row), or stop if equal. Each step eliminates exactly one row or column, terminating in at most m + n steps — O(m+n), not O(log(mn)), but still much better than checking every cell.

What's the recursive-versus-iterative tradeoff for implementing binary search, in terms of space?

The iterative version uses a fixed handful of variables (low, high, mid) regardless of input size — O(1) extra space. The recursive version pushes a new stack frame for each halving, and since it halves the range about log₂(n) times before hitting a base case, it uses O(log n) extra space for the call stack.

How would you find the square root of a non-negative number to some precision using binary search, given that the input isn't a discrete sorted array?

Search over the range of possible answers rather than an array — set low = 0 and high = n (or a known upper bound), repeatedly check whether mid * mid is less than, greater than, or close enough to n, and narrow the range accordingly, stopping once high - low is smaller than the desired precision. This is 'binary search on the answer': the sorted structure being searched is the space of candidate answers, not a literal array.

What is 'binary search on the answer,' and what property must the answer space have for it to apply, even with no literal sorted array to search?

It applies binary search's halving logic to a range of candidate answers to an optimization/feasibility problem, useful when you can cheaply check 'is this candidate answer feasible?' and that feasibility is monotonic — once a candidate value works, every candidate on one side of it also works. That monotonic yes/no boundary is exactly what lets you discard half the remaining candidates on each check, the same way a sorted array lets you discard half the remaining elements.

Give an example of a problem solved with 'binary search on the answer' that has nothing to do with searching an array.

'Find the minimum eating speed k such that a set of banana piles can all be eaten within h hours.' Instead of searching an array, binary search over possible values of k from 1 to the largest pile size — for each candidate k, check in O(n) whether eating at that speed finishes within h hours (a monotonic condition: if a given k works, every larger k also works), narrowing the range of candidate k values accordingly, giving O(n log(max pile size)) overall instead of testing every possible speed one by one.

What is exponential (galloping) search, and when is it more appropriate than plain binary search?

Used when the array's size is unknown or effectively unbounded — start by checking index 1, then double the index (2, 4, 8, 16...) until the value there is >= the target or you run past the end, then run ordinary binary search within the last-known bounding range. This finds a target at position p in O(log p) time, without needing to know the array's length upfront the way plain binary search does.

What is ternary search, and why doesn't it beat binary search for simply finding a value in a sorted array?

Ternary search splits the current range into three parts using two midpoints, discarding one third of the range per comparison instead of one half. While its recursion depth is O(log₃ n) — fewer levels than binary search's O(log₂ n) — each level does two comparisons instead of one, so the total comparisons end up roughly the same order (or slightly worse in practice); it doesn't provide an asymptotic improvement for plain element-search, and is mainly useful for finding the peak of a unimodal function instead.

Why does binary search silently give a wrong answer on unsorted data instead of erroring out?

Binary search's halving logic assumes that if the middle element is too small, everything to its left is also too small (and the reverse for too large) — a guarantee only sortedness provides. On unsorted data that assumption can be false, but the algorithm still runs to completion and returns some index or -1 with total confidence, with no way to detect the violated assumption — it may report 'not found' for a value that's present, or return the wrong index entirely.

Compare a hash table lookup to binary search for finding a value — when would you prefer O(log n) binary search over O(1) average hash table lookup?

Prefer binary search (over a sorted array) when you also need operations a hash table can't do efficiently — range queries, finding the minimum/maximum, or ordered iteration — since a hash table has no concept of key order. If all that's needed is an exact-value lookup with no ordering requirement, a hash table's O(1) average is strictly faster than binary search's O(log n).

If you only need to perform a single search on data that isn't already sorted, is it worth sorting the array first to enable binary search?

No — sorting costs O(n log n), plus an additional O(log n) to binary search, for a total of O(n log n) — strictly worse than just scanning the unsorted array once for O(n). Sorting only pays off if the search (or many searches) will be performed repeatedly on the same data, since the sort cost then amortizes across all of them.

What's the time complexity of finding both the first and last position of a target value in a sorted array with duplicates, using two separate binary searches?

O(log n) total — each of the two searches (leftmost-occurrence and rightmost-occurrence) independently runs in O(log n), and doing two independent O(log n) searches is still O(log n) overall, since constants don't change the complexity class.

What is the relationship between binary search and a binary search tree (BST)?

A BST generalizes the same halving idea — go left if the target is smaller, right if larger — to a dynamic, linked structure instead of a static contiguous array. A balanced BST supports search and O(log n) insertion/deletion, whereas binary search on a plain sorted array is O(log n) for search alone but O(n) for insertion, since inserting in the middle requires shifting every later element to keep it sorted.

Trace a binary search for `target = 2` on `[1, 2, 4, 6, 8, 10]` (indices 0-5), reporting every `low`, `high`, and `mid` along the way.

low=0, high=5: mid=2, arr[2]=4 > 2, so high = 1. low=0, high=1: mid=0, arr[0]=1 < 2, so low = 1. low=1, high=1: mid=1, arr[1]=2 === target — found at index 1.

What happens if you accidentally write `high = mid` instead of `high = mid - 1` in the standard `while (low <= high)` template, when the target is smaller than `arr[mid]`?

Since mid has already been ruled out — it's not equal to the target — leaving it back in the range as the new high means it may be re-examined as a future mid. Depending on how mid is computed, this can produce an infinite loop once low and high become adjacent and mid keeps recomputing to the same index without changing. The fix is symmetric: exclude the just-checked mid from the next range on both sides.

What's the difference in `mid` calculation risk between `Math.floor((low + high) / 2)` and using bitwise `(low + high) >> 1` in JavaScript for very large arrays?

Math.floor operates on JavaScript's regular double-precision numbers, which represent integers exactly up to 2^53 — far beyond any realistic array length. The bitwise >> operator first coerces its operands to 32-bit signed integers, so for an array long enough that low + high exceeds about 2^31, the bitwise version would silently wrap around and compute the wrong midpoint — a real, if rare, trap the Math.floor version doesn't share.

How would you find a 'peak element' in an array (one greater than both its neighbors) using a binary-search-like approach, even though the array isn't sorted?

Compare arr[mid] to arr[mid + 1]. If arr[mid] < arr[mid + 1], a peak must exist somewhere to the right (values are still climbing), so search the right half; otherwise, a peak exists at mid or to its left, so search the left half (inclusive of mid). This works without full sortedness because the comparison still reliably indicates which direction guarantees a peak, letting you discard half the array each step — O(log n).

Why is it important that binary search's loop always makes forward progress, and what's a bug pattern that violates this?

If low/high don't strictly shrink on some iteration, the loop can spin forever without reaching its termination condition. A common bug: using mid = Math.floor((low + high) / 2) together with low = mid (instead of mid + 1) when narrowing to the right half — if low and high become adjacent (e.g. low=3, high=4), mid computes to 3, and setting low = mid leaves low unchanged, looping forever on the same range.

Scenario: you're building an autocomplete feature backed by a large sorted list of terms, and need 'all terms that start with prefix P.' How would binary search help, beyond just finding one exact match?

Binary search twice — once to find the leftmost position where a term is >= P (the start of the matching range), and once to find the leftmost position where a term is >= the 'next' prefix after P (e.g. incrementing P's last character), marking the end of the matching range. Everything between those two boundaries starts with P. Both searches are O(log n), so the whole range is found in O(log n) rather than scanning linearly.

What's the time complexity of binary search in terms of the number of comparisons, precisely, and how does that relate to the O(log n) Big-O statement?

Precisely, binary search takes at most ⌊log₂(n)⌋ + 1 comparisons in the worst case. The Big-O notation O(log n) captures the same growth rate but drops the exact constant and base, since changing the logarithm's base only scales it by a constant factor, which Big-O ignores.

Why does binary search's advantage over linear search grow more dramatic as the input size increases, rather than staying at a fixed multiple?

Linear search's cost scales directly with n — double the input, double the worst-case comparisons — while binary search's cost scales with log₂(n) — double the input, and comparisons only increase by one. So the ratio of linear-search cost to binary-search cost keeps growing as n grows — at 1,000 items it's roughly 1,000 vs. 10 comparisons, but at 1,000,000,000 items it's roughly 1,000,000,000 vs. 30, an enormously larger gap.

Does binary search still work correctly on an array sorted in descending order?

Not with the standard ascending-order comparison logic — the algorithm needs to know which direction 'smaller' values lie in to decide whether to keep the left or right half. It still runs in O(log n) once adapted, but the comparisons must be flipped (search left when arr[mid] is too small, right when too large — the reverse of the ascending version); using the unmodified ascending-order logic on descending data produces incorrect results, similar to running it on unsorted data.