Part 1 · Concepts · Sorting and searching
Binary search templates
Halve the search space every step. Works on sorted data, and on any yes/no question whose answer flips once.
How it works
Use one template everywhere: lo = 0, hi = n (exclusive), loop while lo < hi, and move toward the first index where a condition becomes true. lowerBound is the first a[i] >= x. upperBound is the first a[i] > x. Their difference counts occurrences. 'Search on the answer': if 'can it be done with capacity c' is no, no, no, yes, yes, binary search over c instead of over an array.
| search | O(log n) |
| search on the answer | O(log(range) × cost of one check) |
Reach for it when
- Sorted array: find, insert position, count of x
- Minimum capacity, speed or time that works
- Maximum value that still fits
Implementation (JavaScript, tested)
// first index with a[i] >= x (where x would be inserted)
function lowerBound(a, x) {
let lo = 0,
hi = a.length;
while (lo < hi) {
const m = (lo + hi) >> 1;
if (a[m] < x) lo = m + 1;
else hi = m;
}
return lo;
}
// first index with a[i] > x
function upperBound(a, x) {
let lo = 0,
hi = a.length;
while (lo < hi) {
const m = (lo + hi) >> 1;
if (a[m] <= x) lo = m + 1;
else hi = m;
}
return lo;
}
// "Search on the answer": smallest truck capacity that ships all packages, in order, within `days`
function shipWithinDays(weights, days) {
const fits = cap => {
let used = 1,
load = 0;
for (const w of weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used <= days;
};
let lo = Math.max(...weights),
hi = weights.reduce((s, w) => s + w, 0);
while (lo < hi) {
const m = (lo + hi) >> 1;
if (fits(m)) hi = m;
else lo = m + 1;
}
return lo;
}Traps
- Off by one: stick to one template (lo < hi, hi = mid, lo = mid + 1).
- Infinite loop: with lo < hi, always set lo = mid + 1 on one side.
- The search-on-answer bounds must be valid: lo = biggest single item, hi = everything at once.
In real systems: Every B+tree index lookup is binary search inside nodes. git bisect is binary search over commits. Capacity planning: smallest instance size that meets the SLA.
Say out loud: The check is monotonic, if capacity c works then anything larger works, so I can binary search the answer.