Binary Search

Overview

Binary search finds a target in a sorted collection by repeatedly comparing it with the middle element and discarding the half that cannot contain it. Every comparison removes about half of the remaining candidates, so a million sorted items need at most 20 comparisons.

The core idea is bigger than searching arrays. Binary search works on any search space where a yes/no question is monotonic: once the answer becomes true, it stays true. That is why the same technique solves problems like finding the minimum ship capacity, the first bad software version, or the square root of a number.

When to use it

• The input is sorted, or the answer space is ordered (numbers, indexes, time, capacity).
• You can write a predicate that is false for one prefix and true for the rest (monotonic).
• You need better than O(n) lookups and the data supports O(1) random access.
• The problem says: minimum value that satisfies..., maximum value such that..., first or last position of...

Problem patterns it solves

Where it is used in real software

Key terms

Search space

The range of indexes still able to contain the answer, usually [low, high].

mid

The index being inspected: low + floor((high - low) / 2).

Invariant

If the target exists, it is always inside [low, high]. Every update must preserve this.

Monotonic predicate

A condition that is false...false then true...true across the search space.

Lower bound

The first index whose value is greater than or equal to the target.

How it works, step by step

1. 1
   Initialize the range

   Set low = 0 and high = n - 1. The whole array is the search space.

2. 2
   Pick the middle

   Compute mid = low + floor((high - low) / 2). This form avoids integer overflow in languages with fixed-size integers.

3. 3
   Compare

   If values[mid] equals the target, return mid. The search is complete.

4. 4
   Discard the left half

   If values[mid] < target, the target can only be to the right, so set low = mid + 1.

5. 5
   Discard the right half

   If values[mid] > target, the target can only be to the left, so set high = mid - 1.

6. 6
   Stop when the range is empty

   Loop while low <= high. When low passes high, no candidates remain and the target is absent; return -1. At that moment low is the index where the target would be inserted.

Search for 73 in 10 sorted values

values = [4, 11, 18, 29, 37, 51, 64, 73, 82, 96], target = 73

Only 2 comparisons were needed instead of 8 for a left-to-right scan. Searching for 72 continues: low = 5, high = 6, mid = 5 (51 < 72, low = 6), mid = 6 (64 < 72, low = 7). Now low > high, so the result is -1 and 7 is the insertion position.

Implementation

1function binarySearch(values: number[], target: number): number {2  let low = 0;3  let high = values.length - 1;4 5  while (low <= high) {6    const mid = low + Math.floor((high - low) / 2);7 8    if (values[mid] === target) return mid;9    if (values[mid] < target) {10      low = mid + 1;   // target is in the right half11    } else {12      high = mid - 1;  // target is in the left half13    }14  }15 16  return -1; // low is the insertion point17}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Computing mid as (low + high) / 2 in Java, C, or C++.

  Fix: Use low + (high - low) / 2 so large indexes cannot overflow.

• Writing low = mid with while (low < high) and floor division.

  Fix: When high = low + 1, mid equals low forever. Use low = mid + 1, or round mid up when low = mid is required.

• Mixing inclusive [low, high] and half-open [low, high) conventions.

  Fix: Choose one. Inclusive uses high = n - 1, low <= high, high = mid - 1. Half-open uses high = n, low < high, high = mid.

• Running binary search on unsorted data.

  Fix: The discard rule relies on ordering; verify or sort the input first.

• Returning any match when the problem asks for the first or last.

  Fix: Continue narrowing after a match and remember the best index found so far.

Interview questions

Practice problems