Binary Search
Binary search finds a value in sorted data in O(log n) by halving the search range each step. A template that avoids off-by-one errors and endless loops.
Binary search finds a value in sorted data by repeatedly looking at the middle item and discarding the half that cannot contain the answer. A million items take about 20 steps.
The idea
Looking for a word in a printed dictionary, you do not read from page one. You open it near the middle, see whether your word comes before or after that page, and ignore the other half. Binary search is that process, repeated until the range is empty or the item is found.
It works only because the data is sorted: one comparison with the middle item tells you something about every item on one side of it.
When to use it
- The data is sorted, or can be sorted once and searched many times.
- You need the position of a value, or the place where a value would be inserted.
- The problem asks for O(log n) time.
- More generally: there is a yes-or-no question whose answer switches from "no" to "yes" exactly once as you move through the range, and you need the switching point.
Template 1: find an exact value
function binarySearch(sorted, target) {
let lo = 0;
let hi = sorted.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) {
lo = mid + 1; // target can only be to the right
} else {
hi = mid - 1; // target can only be to the left
}
}
return -1;
}lo and hi are both inclusive: at every step, if the target exists it lies somewhere from lo to hi. The loop runs while that range holds at least one item, which is why the condition is lo <= hi.
Walkthrough
binarySearch([-1, 0, 3, 5, 9, 12], 9):
| lo | hi | mid (value) | Compare with 9 | Action |
|---|---|---|---|---|
| 0 | 5 | 2 (3) | Smaller | lo = 3 |
| 3 | 5 | 4 (9) | Equal | Return 4 |
Two looks at an array of six. And for a target that is missing, such as 2:
| lo | hi | mid (value) | Compare with 2 | Action |
|---|---|---|---|---|
| 0 | 5 | 2 (3) | Larger | hi = 1 |
| 0 | 1 | 0 (-1) | Smaller | lo = 1 |
| 1 | 1 | 1 (0) | Smaller | lo = 2 |
| 2 | 1 | The range is empty | Return -1 |
Template 2: find the insertion point
Sometimes the value may be missing and you need to know where it belongs. This version returns the first index whose value is greater than or equal to the target, often called the lower bound.
function lowerBound(sorted, target) {
let lo = 0;
let hi = sorted.length; // one past the end: the answer may be "after everything"
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (sorted[mid] < target) {
lo = mid + 1;
} else {
hi = mid; // mid might be the answer, so keep it
}
}
return lo;
}Here hi is exclusive, the loop condition is lo < hi, and hi = mid keeps the middle item in play. The two templates should not be mixed: pick one and use its three parts together.
Walkthrough
lowerBound([1, 3, 5, 6], 2):
| lo | hi | mid (value) | Is it less than 2? | Action |
|---|---|---|---|---|
| 0 | 4 | 2 (5) | No | hi = 2 |
| 0 | 2 | 1 (3) | No | hi = 1 |
| 0 | 1 | 0 (1) | Yes | lo = 1 |
| 1 | 1 | lo and hi have met | Return 1 |
The answer, 1, is where 2 would be inserted: between the 1 and the 3.
Template 3: search for an answer, not an item
Binary search does not need an array. It needs a range of possible answers and a yes-or-no test that is "yes" for every answer up to some point and "no" for every answer after it. The search finds that point.
The whole-number square root is a small example. The possible answers are 0 to n, and the test is "is this number squared no more than n?".
// The largest whole number whose square is at most n.
function integerSquareRoot(n) {
let lo = 0;
let hi = n;
while (lo < hi) {
// Round the middle UP, so that lo = mid always makes progress.
const mid = lo + Math.ceil((hi - lo) / 2);
if (mid * mid <= n) {
lo = mid; // mid passes the test: the answer is mid or higher
} else {
hi = mid - 1; // mid fails: the answer is lower
}
}
return lo;
}For n = 17 the test passes for 0, 1, 2, 3 and 4, and fails from 5 onwards, so the function returns 4.
The middle is rounded up here, not down. When the range is two numbers wide and the middle is rounded down, mid equals lo, and lo = mid changes nothing: an endless loop. The rule is that whichever side keeps mid decides the rounding. hi = mid goes with rounding down; lo = mid goes with rounding up.
The same shape solves problems that do not look like searches at all: the smallest lorry that can deliver a set of parcels within five days, the lowest speed that finishes a job on time, the largest minimum gap between items placed in fixed positions. In each one, a candidate answer can be tested quickly, and bigger candidates are always at least as likely to pass.
How few steps it takes
| Items | Steps at most |
|---|---|
| 10 | 4 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
Multiplying the input by a thousand adds ten steps.
Variations
| Problem | What changes | Example |
|---|---|---|
| First or last position of a repeated value | Use the lower-bound template | Search Insert Position |
| Sorted array that has been rotated | Decide which half is in order before choosing a side | Rotated sorted arrays |
| Values that rise to a peak, then fall | Compare the middle with its neighbour to see which slope you are on | Peak finding |
| A grid with sorted rows and columns | Start at a corner and discard a row or a column at each step | Matrix search |
| Two sorted arrays | Search for where to cut one of them | Median of Two Sorted Arrays |
| No array at all | Search the range of answers | Binary search on the answer |
Complexity
- Time: O(log n). The range halves each step. Doubling the input adds one step.
- Space: O(1). Only the two bounds and the midpoint are stored.
Common mistakes
- Searching unsorted data. The result is meaningless, and no error tells you so.
- An endless loop. Writing
lo = midinstead oflo = mid + 1can leave the range unchanged when it has two items. Every branch must make the range smaller. - Mixing the templates. An inclusive
hiwithlo < hi, or an exclusivehiwithhi = mid - 1, skips items. - Calculating the middle as
(lo + hi) / 2. In JavaScript this can give a fraction, so it needsMath.floor. In languages with fixed-size integers,lo + hican also overflow;lo + (hi - lo) / 2avoids that, which is why the templates use it. - Rounding the middle the wrong way.
lo = midwith the middle rounded down loops for ever on a range of two. See Template 3. - Sorting just to search once. Sorting costs O(n log n). For a single lookup in unsorted data, a plain loop at O(n) is faster.
Practise
- Binary Search (easy): Template 1.
- Search Insert Position (easy): Template 2.
- Search in Rotated Sorted Array (medium): finding the half that is in order.
- Median of Two Sorted Arrays (hard): searching for a cut.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Binary Search | easy | O(log n) | O(1) | Short read: 4 min |
| Search Insert Position | easy | O(log n) | O(1) | Short read: 4 min |
| Search in Rotated Sorted Array | medium | O(log n) | O(1) | Medium read: 6 min |
| Median of Two Sorted Arrays | hard | O(log(min(m, n))) | O(1) | Medium read: 8 min |