Algorithm

Binary Search

Find a value in a sorted array by checking the middle and throwing away the half that can't contain it. Each step halves the search space, so a million items take about 20 comparisons instead of up to a million.

TimeO(log n)
SpaceO(1)
NeedsSorted data
1M items≈ 20 steps

Try It — Animated Flow

3
0
8
1
12
2
17
3
23
4
31
5
42
6
56
7
64
8
77
9
85
10
91
11
A sorted array of 12 numbers (indexes below each box). Pick a target and press Run.
Step 1 / 1
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

git bisect
Finds the commit that broke a build by testing the middle commit and halving the range: 1,000 commits take about 10 checks.
Dictionaries and phone books
Open near the middle, then go left or right. It's the same trick people use without thinking about it.
Database indexes
B-tree indexes apply the same idea across disk pages, so a lookup reads a handful of pages instead of every row.
Autocomplete and ranges
Lower bound finds the first word with a prefix (or the first date in a range) in a sorted list; then you just read forward.

Trade-offs

Reach for binary search when
  • The data is sorted and you can jump to any index (an array)
  • You search the same data many times and it rarely changes
  • You need a boundary: the first value ≥ x, or where a range starts
Avoid it when
  • The data is unsorted and you search once (sorting costs more than one scan)
  • It's a linked list: you can't jump to the middle
  • Items are added constantly (a BST or hash table stays fast as it changes)