Binary Search · Optimal Solution

Halving the search space, one comparison at a time.

A library's digital catalog holds 200,000 titles sorted alphabetically. Rather than scanning from A to Z, you open to the middle and discard half — repeating until the answer emerges. Two pointers, low and high, define the surviving interval; each comparison shrinks it by half. The answer arrives in O(log n) comparisons.

Interactive

Watch the interval shrink

Concept

Three pointers, one invariant

The algorithm maintains a single invariant: the target, if present, is somewhere between low and high inclusive. Every comparison shrinks that window by half.

low

Left boundary of the search interval. Moves right when the midpoint value is too small.

low = mid + 1

high

Right boundary of the search interval. Moves left when the midpoint value is too large.

high = mid − 1

mid

Computed each iteration as low + (high − low) / 2. The value at mid is compared with the target.

avoids overflow
Algorithm

Each iteration halves the interval

The outer condition while (low ≤ high) ensures we stop once the interval has collapsed — meaning the target is absent.

  1. 1

    Compute midpoint

    Calculate mid = low + (high − low) / 2. This formula avoids integer overflow.

  2. 2

    Compare mid value with target

    Read nums[mid] and check if it equals, is less than, or is greater than the target.

  3. 3

    Discard a half

    If nums[mid] < target, the answer must be to the right → set low = mid + 1. If nums[mid] > target, the answer must be to the left → set high = mid − 1. If equal, we have found it.

  4. 4

    Repeat or terminate

    Loop continues until low > high (target absent) or the target is found.

Edge Cases

When the search fails

Binary search does not always find its target. Understanding the failure mode is as important as understanding the success path.

Target absent

When low crosses past high, the search interval is empty. No element in the array equals the target. The algorithm returns −1. Try the "target absent" preset to watch the interval collapse.

Single element

When the array has just one element, low = high = 0 and mid = 0. A single comparison resolves the answer immediately. Try the "single element" preset.