Binary Search

Binary search is a deceptively simple algorithm that finds a value in a sorted array in O(log n) time. Even with a billion items, it takes about 30 comparisons to find what you're looking for. The catch: the array must be sorted first.

The Idea

You don't scan one element at a time. You look at the middle, compare it to the target, and:

If the middle is your target, you're done.
If the middle is too small, the target must be in the right half. Throw away the left half.
If the middle is too big, the target must be in the left half. Throw away the right half.

Each step halves the remaining search space. After k steps, you're searching at most n / 2^k items. You hit one item after about log₂(n) steps.

Why log n Matters

Linear search is O(n). Binary search is O(log n). The difference at scale is enormous:

1,000 items: linear ~1,000 steps, binary ~10 steps
1,000,000 items: linear ~1,000,000 steps, binary ~20 steps
1,000,000,000 items: linear ~1 billion steps, binary ~30 steps

This is why sorted lookup tables, indexed databases, and library search APIs all rely on binary-search-like algorithms.

Common Pitfalls

Binary search is famously easy to get wrong. Watch out for:

Off-by-one in the loop condition. low <= high (inclusive high) versus low < high (exclusive high) — pick one and stick with it.
Forgetting to update bounds. low = mid + 1, not low = mid. Otherwise the loop never terminates.
Integer overflow. (low + high) / 2 can overflow with very large indices. Use low + (high - low) / 2 in C++ and Java.
Searching an unsorted array. Binary search silently produces wrong answers on unsorted data. Always confirm sortedness.

Variations

The same template adapts to many problems: first occurrence, last occurrence, insertion point, or "search a value in a rotated sorted array." Each variation tweaks the comparison and what you return when arr[mid] == target.

Try It Yourself

Modify binary search to return the first index of a target that appears multiple times
Find the insertion index for a target that's not in the array (where it would go to keep things sorted)
Use binary search to compute integer square root: find the largest k such that k*k <= n