What is Binary Search
Binary search finds a target value in a sorted collection by repeatedly cutting the search space in half. Instead of scanning every element, it compares the target to the middle element and eliminates the half where the target cannot exist. This runs in O(log n) time — searching a million items takes about 20 comparisons, not a million.
How it works
Start with a sorted array. Compare the target to the middle element:
- If they match, you found it.
- If the target is smaller, repeat on the left half.
- If the target is larger, repeat on the right half.
Each step halves the remaining elements. For an array of 1,024 items, after 10 comparisons you've narrowed it to 1 element.
Searching for 7 in [1, 3, 5, 7, 9, 11, 13]:
Step 1: mid = 7 → found
Searching for 3 in [1, 3, 5, 7, 9, 11, 13]:
Step 1: mid = 7 → 3 < 7, search left [1, 3, 5]
Step 2: mid = 3 → found
The critical requirement is that the data must be sorted. Binary search on unsorted data gives wrong results. This is why sorting and searching are deeply linked — the cost of sorting is an investment that pays off across many searches.
Binary search is also the principle behind binary search trees. In a BST, every node acts as a midpoint: left children are smaller, right children are larger. The tree structure makes the same halving decision at each node, achieving O(log n) lookups without needing a sorted array.
Beyond exact matches, binary search solves boundary problems: finding the first element greater than a value, the insertion point for a new element, or the leftmost duplicate.
Why it matters
Binary search is the most important algorithm you will use routinely. It appears in database index lookups, language runtime libraries (every standard library's "find" on sorted data), git bisect (finding the commit that introduced a bug), and any problem where you need fast lookup in ordered data. Understanding it deeply — especially the off-by-one edge cases — pays off every day.
See How Searching Works for the full treatment.