Binary search — halving a sorted array

Searching a sorted list of 1,000,000 items for one value — how many comparisons do you need? Scanning from the front takes up to 1,000,000. Binary search does it in 20.

The whole difference comes from one idea: discard the other half every round.

What you'll learn in this chapter

• How binary search narrows the range
• Why time complexity is O(log n) and space complexity is O(1)
• Three common implementation pitfalls
• The conditions where it applies, and where it doesn't

Prerequisites

This chapter builds on big-O and the conditions that produce logs from Complexity.

Halving each time

Find 7 in the sorted array [1, 3, 5, 7, 9, 11, 13, 15].

Found on the first try. If instead we were looking for 11, since it's greater than the middle 7, we discard the whole left half and search only the right. We can discard because the array is sorted, and "definitely not on the left" holds.

Repeat.

Round	Range	Middle	Decision
1	1 3 5 7 9 11 13 15	7	11 > 7 → right half
2	9 11 13 15	11	Equal

Eight elements in two rounds.

Following the steps by index

The search range is held in two indices: left is the left edge, right the right edge, and the array is called array below.

1. Pick the middle mid of the range: halfway between left and right, rounded down
2. Compare array[mid] with the target. If they match, mid is one of the answers
3. If the target is larger, the answer lies to the right of the middle. Move left to mid + 1
4. If the target is smaller, the answer lies to the left of the middle. Move right to mid - 1
5. Stop once left becomes greater than right. The range is empty, so the target is not present

Here is the search for 11 from the previous section, rewritten with those indices.

Round	left	right	mid	array[mid]	Decision
1	0	7	3	7	7 < 11, so left = 4
2	4	7	5	11	Equal. Return 5

Searching for a value that isn't in the array ends with an empty range. Here is 14.

Round	left	right	mid	array[mid]	Decision
1	0	7	3	7	7 < 14, so left = 4
2	4	7	5	11	11 < 14, so left = 6
3	6	7	6	13	13 < 14, so left = 7
4	7	7	7	15	15 > 14, so right = 6

Nothing along the way tells you the value is absent. On the fourth round right becomes 6, dropping below left at 7, and with the range empty it returns -1.

Implementation

/** Search a sorted ascending array for target; return one matching index, or -1 */
function binarySearch(array: number[], target: number): number {
  let left = 0;
  let right = array.length - 1;

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

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      left = mid + 1; // Must be to the right of the middle
    } else {
      right = mid - 1; // Must be to the left of the middle
    }
  }

  return -1;
}

Two points to read for:

• left and right represent the search range. The invariant maintained throughout is that the answer isn't outside this range
• mid + 1 and mid - 1. The middle is already compared, so it's excluded from the range. Leaving it as mid prevents the range from shrinking, causing an infinite loop

Complexity

Time complexity is O(log n). The range halves each iteration, so bringing n down to 1 takes log₂ n rounds. The last remaining element still needs one comparison, so the maximum number of comparisons is log₂ n rounded down, plus 1.

Elements	Max comparisons
8	4
1,000	10
1,000,000	20
1,000,000,000	30

Multiplying items by 1,000 adds only 10 comparisons. That's how logs behave.

Space complexity is O(1). Only left, right, and mid are used, and they don't grow with input size. The input array isn't extra memory.

Recursion changes the space

The same algorithm as recursion has space complexity O(log n).

function binarySearchRecursive(
  array: number[],
  target: number,
  left = 0,
  right = array.length - 1,
): number {
  if (left > right) return -1;

  const mid = left + Math.floor((right - left) / 2);
  if (array[mid] === target) return mid;
  if (array[mid] < target) {
    return binarySearchRecursive(array, target, mid + 1, right);
  }
  return binarySearchRecursive(array, target, left, mid - 1);
}

Time complexity matches the iterative version at O(log n), but the call stack piles up to depth log n, growing space. A case where the same algorithm has different space complexity depending on how it's written. The design of recursion and when depth matters is covered in Recursion and divide-and-conquer.

Implementation pitfalls

1. Computing the midpoint

(left + right) / 2 is the natural form, but in languages with fixed-width integers left + right can overflow. If both are near the maximum, the sum wraps to a negative and the index breaks.

const mid = left + Math.floor((right - left) / 2); // Safe

right - left is always non-negative and never exceeds right, so this form doesn't overflow. JavaScript's numbers are 64-bit floats, so realistic arrays don't hit this — but this form has spread as the idiom, so it's worth being able to read.

2. Boundary conditions

Changing left <= right to left < right causes the loop to exit while one element remains uncompared. If you treat the range as the closed interval [left, right], the continuation condition is <=.

3. The range doesn't shrink

In this closed-interval form with left <= right, writing left = mid or right = mid causes the range to stop shrinking the moment mid equals left, giving an infinite loop. Exclude the compared mid from the range.

When it applies

Binary search is correct under one condition: the range can be split into "before the answer" and "after the answer". To also get the speed, you need one more: constant-time access to the middle.

The most common shape is "sorted array", but not only that.

Applies	Doesn't apply
Ascending or descending sorted array	Unordered data
Structures with random access by index	Linked lists (can't reach the middle in one step)
Problems where "≥ some value" is monotonically decidable	Problems where the decision is not monotonic

Binary search on a linked list isn't faster. Reaching the middle from the head takes O(n). Binary search's speed depends on jumping to the middle by index in constant time. Access-cost differences by structure are covered in Choosing data structures.

If you'll search only once, sorting first and then binary searching is a loss. Sorting takes O(n log n), worse than linear search's O(n). It pays off only when you search the sorted array many times.

With duplicate values, the returned index is any one of the matches. If you need the first match, use the findBoundary shape below, which narrows the boundary with high = mid.

Uses without a sorted array

If there's a monotonic decision, it doesn't have to be an array.

/** Find the smallest value satisfying the condition. judge is false before the boundary and true from there on */
function findBoundary(low: number, high: number, judge: (x: number) => boolean): number {
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (judge(mid)) {
      high = mid; // Since it satisfies, nothing larger is needed
    } else {
      low = mid + 1;
    }
  }
  return low;
}

In this form the continuation condition is low < high, so high = mid is correct: mid can itself be the answer, and low < high guarantees mid < high, so the range always shrinks.

Problems like "how many servers make processing time drop below the target" — where the candidate answers line up and the decision is monotonic — reduce to this shape. It's called "binary search on the answer" since you binary-search on the answer itself.

Common misconceptions

"Binary search works on any array." — It doesn't. Sorted (or a monotonic decision) is a prerequisite.

"Binary search has space complexity O(log n)." — Iteratively it's O(1). It becomes O(log n) only in the recursive version's call stack.

"Even on linked lists, binary search is faster." — It isn't. Reaching the middle is O(n), and the overall performance matches linear search.

"If you want to search, just sort first." — For a single lookup, sorting's O(n log n) is more expensive. Linear search at O(n) suffices.

Exercises

Q1. State the time and space complexity of the binarySearch function above.

Answer and explanation

Answer: Time O(log n), space O(1)

Time: on each while iteration, either left or right moves past mid, halving the range. Bringing the range from n to 1 takes log₂ n rounds.

Space: only left, right, and mid are allocated — three values regardless of n. The input array isn't extra memory. No recursion, so no call stack.

A common wrong answer is O(n). When there's a loop, the reflex is linear — but each iteration halves the remaining work, so it's logarithmic. Look at how state changes per iteration, not just at the presence of a loop.

Q2. This implementation has a bug. Where?

function buggySearch(array: number[], target: number): number {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (array[mid] === target) return mid;
    if (array[mid] < target) {
      left = mid;
    } else {
      right = mid;
    }
  }
  return -1;
}

Answer and explanation

Answer: left = mid and right = mid fail to shrink the range and cause an infinite loop.

Consider two elements left. left = 0, right = 1 gives mid = 0 + Math.floor(1/2) = 0.

• If array[0] < target, then left = mid = 0. Neither left nor right changes
• Next iteration also gives mid = 0, repeating the same comparison

mid has already been compared, so it must be excluded from the range.

left = mid + 1;   // Correct
right = mid - 1;  // Correct

Q3. You search once against a 100,000-element array. Which is faster: "sort then binary search" or "linear search as-is"?

Answer and explanation

Answer: Linear search

• Sort + binary search — O(n log n) + O(log n), effectively O(n log n)
• Linear search — O(n)

With n = 100,000, log₂ n is about 17, so sorting costs about 17× more than linear search. A single lookup doesn't earn back the sort.

The break-even point comes with more searches. For k searches:

• Sort + k binary searches — O(n log n + k log n)
• k linear searches — O(k n)

Sort wins once k passes about log n (~17). "How many searches" is the input to the decision. It's the same structural decision as whether to add a database index.

Summary

• Binary search achieves O(log n) by discarding half the range each round
• Time complexity O(log n), space complexity O(1) (iterative)
• Written recursively, space complexity becomes O(log n) because of the call stack
• The midpoint idiom is left + (right - left) / 2
• In the closed-interval [left, right] form, exclude the compared mid via mid + 1 / mid - 1. Failing to exclude it causes infinite loops
• Prerequisites: sorted (or monotonic decision) and constant-time access to the middle
• For a single lookup, linear search is faster than sorting first

Related references

• Database Design Guide — Introduction to index design — A B-Tree realizing the same "halve each round" idea inside a database

What to read next

• Choosing data structures — Which structures binary search works on, and which it doesn't
• Recursion and divide-and-conquer — Rereading binary search as a special case of divide-and-conquer