Binary Search
A decision-to-answer pattern for monotone predicates, answer-space search, and continuous approximation.
Binary Search
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Binary search is not really about sorted arrays. The broader pattern is: there is an ordered search space, and once a candidate becomes valid, everything on one side stays valid as well. Then I can replace a linear scan with repeated halving.
In contests this appears in several forms: searching inside a sorted container, finding the first time a process becomes feasible, and binary searching an answer when the real work is hidden inside a checker.
When to Use It
Use binary search when:
the search space is ordered,
the predicate is monotone,
checking one candidate is much cheaper than trying every candidate,
the final answer is a boundary such as ``first valid'', ``last valid'', or an approximate real value.
Typical examples are minimum capacity, maximum achievable score, smallest time, or first position where a prefix condition becomes true.
Core Idea
Maintain an interval that is guaranteed to contain the answer. At each step, evaluate the middle point and throw away the half that cannot contain the boundary anymore.
For a first-true search on integers, I keep the invariant: \[ \texttt{answer} \in [lo, hi], \qquad \texttt{pred(hi) = true}. \] If \(\texttt{pred(mid)}\) is true, the answer is in the left half. Otherwise it is in the right half.
Key Insight
The main job is not writing the loop. The main job is choosing a predicate whose truth set is monotone.
For example, if I want the minimum value \(x\) such that some task can be completed, I do not search directly on the construction. I ask a yes/no question: ``Can I do it with limit \(x\)?'' If the answer changes from false to true only once, the problem is ready for binary search.
Operations / Main Technique
Sorted array search.
Use the standard lower-bound / upper-bound interpretation:
first position with value \(\ge x\),
first position with value \(> x\),
last position with value \(\le x\).
Binary search on answer.
Pick a candidate answer \(mid\), run a greedy, DP, or prefix-based checker, and use the result as a monotone predicate.
Real-valued search.
If the answer is a real number, run a fixed number of iterations instead of relying on exact equality.
Worked example.
Suppose I need the smallest machine speed that finishes all jobs within \(T\) hours. If speed \(s\) works, then every speed larger than \(s\) also works. That turns the optimization problem into a first-true boundary search.
Correctness Intuition
Each iteration preserves the invariant that the answer still lies in the active interval. The monotonicity of the predicate guarantees that once one side is rejected, no valid answer is lost with it.
When the interval shrinks to one point, that point must be the boundary we were maintaining.
Complexity Analysis
If the search space has size \(N\), integer binary search needs \(O(\log N)\) predicate calls. The total cost is \[ O(\log N \cdot \text{cost of checker}). \] For real-valued search, the complexity is \(O(k \cdot \text{cost of checker})\), where \(k\) is the chosen iteration count.
Implementation
The reference code includes:
first_trueon integers,last_trueon integers,a floating-point variant with a fixed number of iterations.
I prefer writing these as small templates and keeping the predicate outside. That makes the checker easy to test on its own.
Common Pitfalls
Using binary search without proving the predicate is monotone.
Picking bounds that do not actually contain the answer.
Mixing ``first true'' and ``last true'' logic in the same loop.
Overflow in \(\texttt{mid = (lo + hi) / 2}\) when the bounds are large.
Using binary search on real values when the problem really wants an exact discrete argument.
Variants / Extensions
Exponential search to discover an upper bound before binary search.
Parallel binary search for many offline monotone queries.
Binary lifting style search on Fenwick trees or doubling tables.
Ternary search when the target is unimodal rather than monotone.
Practice Problems
Find the first position of a value in a sorted array with duplicates.
Minimum capacity to ship packages within \(D\) days.
Maximum minimum distance after placing objects greedily.
Binary search on answer where the checker uses prefix sums or greedy feasibility.
References
Code
Contest-ready reference implementation for the idea explained above.
template <class F>
long long first_true(long long lo, long long hi, F pred) {
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (pred(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
template <class F>
long long last_true(long long lo, long long hi, F pred) {
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (pred(mid)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
template <class F>
double binary_search_real(double lo, double hi, F pred, int iterations = 80) {
for (int it = 0; it < iterations; ++it) {
double mid = (lo + hi) * 0.5;
if (pred(mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.