Binary Search

Binary search locates a target value inside a sorted array by comparing the target to the middle element and eliminating half of the remaining search space at each step. Instead of checking elements one at a time like a linear scan, it discards half the candidates with every comparison.

Compare that to linear search, which checks each element in order and, in the worst case, looks at every single one — O(n). Binary search’s halving strategy is what gets it down to O(log n).

Binary search only works because a sorted array lets you make a guarantee at every step: if the middle element is greater than the target, the target — if it exists — must be to the left; if it’s smaller, the target must be to the right. On unsorted data that guarantee doesn’t hold, and the algorithm can’t safely discard half the array.

If your data isn’t already sorted, sorting it first costs O(n log n) (see merge sort) — which only pays off if you plan to search the same data multiple times.

Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] (indices 0–9):

• Step 1:low = 0, high = 9, mid = 4 → value 16. 16 < 23, so search the right half: low = 5.
• Step 2:low = 5, high = 9, mid = 7 → value 45. 45 > 23, so search the left half: high = 6.
• Step 3: low = 5, high = 6, mid = 5 → value 23. Match found at index 5.

Ten elements, found in three comparisons — a linear scan could have taken up to ten.

Each comparison discards half of the remaining elements. Starting from n elements, after one comparison n/2 remain, then n/4, then n/8, and so on. The question “how many halvings does it take to get from n down to 1?” is exactly what log₂(n)answers. For 1,024 elements, that’s only 10 comparisons; for 1,000,000 elements, only about 20.

This is the same halving pattern covered in the time complexity guide’s section on logarithmic behavior.

The space complexity difference between the two implementations matters: the iterative version uses a fixed number of variables regardless of input size, while the recursive version’s call stack grows with each halving — O(log n) stack frames.

The iterative version uses O(1) auxiliary space:

function binarySearch(sortedNums, target) {
  let low = 0, high = sortedNums.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sortedNums[mid] === target) return mid;
    if (sortedNums[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

The recursive version is often more readable but trades that for O(log n) call-stack space:

function binarySearch(sortedNums, target, low = 0, high = sortedNums.length - 1) {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  if (sortedNums[mid] === target) return mid;
  return sortedNums[mid] < target
    ? binarySearch(sortedNums, target, mid + 1, high)
    : binarySearch(sortedNums, target, low, mid - 1);
}

Both do the same O(log n) number of comparisons — the difference is purely in space, and in most languages the iterative version is preferred for exactly that reason.

• Big-O Cheat Sheet — see where O(log n) ranks among the other complexity classes.
• How to Analyze Time Complexity of Any Algorithm — the general method binary search is a worked example of.
• Merge Sort — the O(n log n) sort you’d use to prepare unsorted data for binary search.
• Space Complexity Explained — why the recursive version above costs O(log n) stack space while the iterative version costs O(1).