Searching
Linear and binary search, how to write binary search without off-by-one bugs using an explicit invariant, every common variant, and binary search on the answer.
What you will learn
Linear and binary search, how to write binary search without off-by-one bugs using an explicit invariant, every common variant, and binary search on the answer.
Prerequisites: Modules 2 and 5.
Linear search
Check elements one by one; time O(n), space O(1).
Binary search
Requires a sorted range or a monotonic predicate. Maintain a valid search interval and a clear invariant.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Use mid = lo + (hi - lo) / 2 rather than (lo + hi) / 2, which overflows when both indices are large. The half-open [lo, hi) style of lowerBound is easier to get right: the loop ends when lo == hi, and the answer is lo.
Python's bisect module provides bisect_left (lower bound) and bisect_right (upper bound); integers never overflow, so (lo + hi) // 2 is safe.
Output (CPython 3.13.1):
#include <bits/stdc++.h>
using namespace std;
int binarySearch(const vector<int>& a, int target) {
int lo = 0, hi = static_cast<int>(a.size()) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// lower bound: first index i with a[i] >= target, in [0, n]. Invariant: a[0..lo) < target, a[hi..n) >= target
int lowerBound(const vector<int>& a, int target) {
int lo = 0, hi = (int)a.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) lo = mid + 1; else hi = mid;
}
return lo;
}
int upperBound(const vector<int>& a, int target) { // first index with a[i] > target
int lo = 0, hi = (int)a.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] <= target) lo = mid + 1; else hi = mid;
}
return lo;
}
int main() {
vector<int> a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23, lo = 0, hi = (int)a.size() - 1, step = 0;
while (lo <= hi) { // dry run
int mid = lo + (hi - lo) /
…step 1: lo=0 hi=9 mid=4 a[mid]=16
step 2: lo=5 hi=9 mid=7 a[mid]=56
step 3: lo=5 hi=6 mid=5 a[mid]=23
binarySearch(23)=5 binarySearch(7)=-1
first 2 at 1, last 2 at 3, count 3, insert position of 4: 5
lowerBound/upperBound match the STL on 5000 random cases
mid via lo + (hi - lo) / 2 = 2147483646; (lo + hi) / 2 would overflow intfrom bisect import bisect_left, bisect_right
def lower_bound(a, x):
lo, hi = 0, len(a) # invariant: a[:lo] < x <= a[hi:]
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
d = [1, 2, 2, 2, 3, 5]
print("lower_bound(2) =", lower_bound(d, 2), "| bisect_left:", bisect_left(d, 2), "| bisect_right:", bisect_right(d, 2))
print("count of 2 =", bisect_right(d, 2) - bisect_left(d, 2))lower_bound(2) = 1 | bisect_left: 1 | bisect_right: 4
count of 2 = 3Required variants
First/last occurrence, lower bound, upper bound, count of occurrences, search insertion position, rotated sorted array, nearly sorted array, bitonic array, 2D matrix search, integer square root, and binary search on the answer.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Binary search on the answer works whenever a yes/no predicate is monotonic in the parameter: if capacity c suffices, every larger capacity also suffices. Search for the boundary between “no” and “yes” instead of searching an array.
#include <bits/stdc++.h>
using namespace std;
int searchRotated(const vector<int>& a, int t) { // distinct values
int lo = 0, hi = (int)a.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == t) return mid;
if (a[lo] <= a[mid]) { // left half is sorted
if (a[lo] <= t && t < a[mid]) hi = mid - 1; else lo = mid + 1;
} else { // right half is sorted
if (a[mid] < t && t <= a[hi]) lo = mid + 1; else hi = mid - 1;
}
}
return -1;
}
long long isqrt(long long n) { // largest x with x*x <= n
long long lo = 0, hi = min<long long>(n, 3'037'000'499LL); // hi*hi fits in long long
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2; // upper middle: the loop keeps lo feasible
if (mid <= n / mid) lo = mid; else hi = mid - 1;
}
return lo;
}
// binary search on the answer: smallest capacity to ship all packages within `days`
bool canShip(const vector<int>& w, int days, long long cap) {
int used = 1; long long load = 0;
for (int x :
…rotated array, index of 6: 4, of 22: 2, of 7: -1
isqrt(0) = 0
isqrt(1) = 1
isqrt(15) = 3
isqrt(16) = 4
isqrt(1000000000000000000) = 1000000000
ship within 5 days: minimum capacity 15Advanced binary search
Search a monotonic feasibility predicate.
Minimize maximum / maximize minimum.
Floating-point binary search and termination criteria.
Exponential search for unbounded/unknown ranges.
Ternary search for unimodal functions, with assumptions clearly stated.
For real-valued answers, loop a fixed number of times (each iteration halves the interval; 100 iterations shrink any double interval below its precision) rather than testing hi − lo > ε, which can loop forever when ε is smaller than the spacing of representable numbers near the answer. Exponential search doubles an upper bound (1, 2, 4, …) until it passes the target, then binary-searches: O(log p) where p is the answer's position.
binsearchQuiz
? Why write `mid = lo + (hi - lo) / 2`?
+ `lo + hi` can overflow int when both are large; the difference cannot. :: The run computed a valid mid near INT_MAX.
- It rounds up. :: It rounds down, like (lo + hi) / 2.
- It is faster. :: Same speed.
- It handles negative arrays. :: Values are irrelevant.
? What makes “binary search on the answer” valid?
+ The feasibility predicate is monotonic in the answer. :: Once feasible, every larger value stays feasible (or vice versa).
- The input array is sorted. :: The array need not be sorted.
- The answer is an integer. :: Real answers work with fixed iterations.
- The input is small. :: Size is irrelevant.
? In the isqrt loop, why `mid = lo + (hi - lo + 1) / 2`?
+ With `lo = mid` on success, the lower middle could make no progress when hi = lo + 1 and loop forever. :: Use the upper middle when the feasible side keeps lo.
- To avoid overflow. :: The `+1` is about progress.
- It is arbitrary. :: It prevents an infinite loop.
- To find the ceiling square root. :: It finds the floor.