Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Start with a search window covering the entire sorted array (lo = 0, hi = length - 1).
  2. Compute the midpoint of the current window.
  3. If the middle element equals the target, the search succeeds.
  4. If the middle element is less than the target, discard the left half by moving lo past mid.
  5. If the middle element is greater than the target, discard the right half by moving hi before mid.
  6. Repeat until the target is found or the window becomes empty (lo > hi).

Key concepts

  • Requires the input to be sorted
  • Halves the search space on every comparison
  • Iterative, constant extra space (O(1))
  • Logarithmic time complexity — doubling the input adds only one more comparison

When to use it

When searching within already-sorted data, especially repeatedly — the O(log n) lookup vastly outperforms a linear scan once the sort cost is amortized across many searches.

Did you know

Despite being conceptually simple, the first published binary search implementation (1946) contained a bug, and a correct, fully-verified version wasn't published until 1962.