~/searching/binary-search
Binary search
Find a value in a sorted array by halving the range on every look. A million elements take at most 20 looks.
Keep a range that must contain the answer. Look at its middle and throw away the half that can't.
The data is sorted, or a yes/no condition flips from false to true exactly once.
O(log n)
O(1)
You’ll recognise it when
- The input is sorted, and you need to find a value or the spot where it would go.
- The question says first or last position where something becomes true.
- A linear scan would work, but
nis 10⁵ or more and there are many queries. - You want the smallest speed, capacity or time that still works, and bigger always works too. That’s binary search on the answer (see Variations).
The idea
Someone picks a number from 1 to 100 and answers each guess with “higher” or “lower”. You wouldn’t guess 1, 2, 3… You’d guess 50: whatever the reply, half the numbers are gone. Seven guesses always suffice, because 2⁷ = 128 is more than 100.
Binary search is that game on a sorted array. Look at the middle element. If it’s smaller than the target, the target can only be in the right half, so drop the left half. Otherwise drop the right half. Every look halves what’s left.
How it works
We’ll write the version that’s most useful in practice, lower bound: return the first index whose value is >= target. One loop answers both “where is it?” and “where would it go?”.
Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the input: try duplicates, a missing value, or a target bigger than everything.
- Keep a half-open range
[lo, hi)that must contain the answer. Start with everything:lo = 0,hi = n. - While the range isn’t empty (
lo < hi), look at the middle,mid = (lo + hi) // 2. - If
a[mid] < target, the answer is right ofmid: setlo = mid + 1. - Otherwise
a[mid]could be the answer, so keep it: sethi = mid. - When
lo == hithe range is empty andlois the answer. To check membership, testlo < n and a[lo] == target.
Why it’s correct: everything left of lo is always < target, and everything from hi on is always >= target. Each step keeps both facts true and shrinks the gap between them, so when the gap closes, lo sits exactly on the boundary.
def lower_bound(a, target):
"""First index i with a[i] >= target, or len(a) if there is none."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def search(a, target):
"""Index of target in a, or -1."""
i = lower_bound(a, target)
return i if i < len(a) and a[i] == target else -1#include <vector>
using namespace std;
// First index i with a[i] >= target, or a.size() if there is none.
int lowerBound(const vector<int>& a, int target) {
int lo = 0, hi = a.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
// Index of target in a, or -1.
int search(const vector<int>& a, int target) {
int i = lowerBound(a, target);
return (i < (int)a.size() && a[i] == target) ? i : -1;
}class BinarySearch {
// First index i with a[i] >= target, or a.length if there is none.
static int lowerBound(int[] a, int target) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
// Index of target in a, or -1.
static int search(int[] a, int target) {
int i = lowerBound(a, target);
return (i < a.length && a[i] == target) ? i : -1;
}
}Why it’s O(log n)
Each pass through the loop at least halves hi - lo. After k passes at most n / 2ᵏ elements remain, so the loop runs at most about log₂ n + 1 times.
| n | looks, worst case |
|---|---|
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
Space is O(1): three integers, no recursion.
Common mistakes
Mixing two range conventions
hi = n - 1 belongs to closed ranges [lo, hi] with while lo <= hi and hi = mid - 1. hi = n belongs to half-open ranges with while lo < hi and hi = mid. Mixing lines from each skips elements or loops forever. Pick one style, and learn all four lines of it together.
Writing lo = mid
When the range has two elements, mid equals lo. If the step is lo = mid, nothing changes and the loop never ends.
lo = mid # ✗ stuck when hi == lo + 1
lo = mid + 1 # ✓ a[mid] < target, so mid itself is ruled out
Overflow in C++ and Java
(lo + hi) / 2 overflows once lo + hi passes 2³¹ − 1, which happens on big arrays or when searching over large answer ranges. Python’s integers never overflow.
int mid = (lo + hi) / 2; // ✗ can overflow
int mid = lo + (hi - lo) / 2; // ✓ same value, no overflow
Reading a[lo] without checking lo
If the target is bigger than every element, the loop ends with lo == n, one past the end. Check lo < n before reading a[lo].
Variations
- Upper bound. The first index with
a[i] > target: change<to<=. The number of copies oftargetisupper − lower, and the last copy is atupper − 1. - Binary search on the answer. The “array” doesn’t exist; you have a check
ok(x)that is false, false, …, then true, true, … Searchxfor the first true. Classic example: the smallest ship capacity that moves every package withinDdays. - Rotated sorted array. One half around
midis always sorted. Compare with that half’s ends to decide whether the target can be there. - Real numbers. For a continuous answer, loop a fixed number of times (say 100) instead of
while lo < hi, and setlo = midorhi = mid. - Library versions. Python
bisect.bisect_left, C++std::lower_bound, JavaArrays.binarySearch. Java returns-(insertion point) - 1when the value is missing, not-1.
Check yourself
5 quick questions. Pick an answer to see why it's right or wrong.
-
1
Packages must ship in order within
Ddays, and you want the smallest daily capacity that manages it. Any bigger capacity works too. What’s the efficient approach?ok(capacity)is false, false, …, then true, true: it flips exactly once, which is all binary search needs, even with no array in sight. Each guess costs one O(n) pass over the packages, so the total is O(n log W) for a capacity range of size W. Counting up from 1 is correct but can take W checks. -
2
What does this print?
def upper_bound(a, x):lo, hi = 0, len(a)while lo < hi:mid = (lo + hi) // 2if a[mid] <= x:lo = mid + 1else:hi = midreturn loa = [2, 4, 4, 4, 7]print(upper_bound(a, 4), upper_bound(a, 9), upper_bound(a, 1))With
<=, the loop finds the first index whose value is greater thanx. The 4s sit at indexes 1 to 3, so that’s 4. Whenxis bigger than everything, the answer islen(a), 5, one past the end, which is why callers checki < len(a)before readinga[i]. Below everything gives 0. -
3
In the half-open lower bound, someone writes
lo = midinstead oflo = mid + 1. What happens witha = [1, 3]andtarget = 5?First pass:
mid = 1anda[1] = 3 < 5, solo = 1. Nowhi == lo + 1, somid = (1 + 2) // 2 = 1again, andlo = midchanges nothing, forever. Sincea[mid] < targetrulesmidout, the right step islo = mid + 1, which ends the loop and returns 2. -
4
What does this print?
from bisect import bisect_left, bisect_righta = [1, 3, 3, 5, 7, 9]print(bisect_right(a, 7) - bisect_left(a, 3), bisect_right(a, 4) - bisect_left(a, 4))bisect_right(a, 7)is 5, one past the last 7, andbisect_left(a, 3)is 1, the first 3, so 5 − 1 = 4 values lie in [3, 7]: 3, 3, 5 and 7. For the missing 4, both calls return the same insertion point, 3, so the count is 0. The same subtraction counts copies of one value, and the last copy sits atbisect_right − 1. -
5
In C++,
loandhiareints holding 1,500,000,000 and 2,000,000,000. What goes wrong withint mid = (lo + hi) / 2;?lo + hiis 3,500,000,000, past theintlimit of 2³¹ − 1 (about 2.1 billion). It overflows before the division happens, and in practice wraps to a negative number.lo + (hi - lo) / 2gives the same midpoint without the big sum. Python’s integers never overflow, so(lo + hi) // 2is fine there.
Practice problems
Solve these right here, in Python, C++ or Java. Tests run as you go.