Binary Search
Binary search over an array and over the answer: O(log n), invariants and typical mistakes.
If the data is sorted (or the condition is monotone: "up to some point — no, after it — yes"), you can search by halving: each step discards half of the candidates. A billion elements — only 30 steps. That is binary search, O(log n).
It must be written carefully: off-by-one errors and infinite loops are the topic's trademark. A reliable template is the half-open interval [l, r): we look for the first index where the condition holds.
The first occurrence of x. Enter: 6 5, then the sorted array 1 3 5 5 7 9
The STL already has this: std::lower_bound(a.begin(), a.end(), x) returns an iterator to the first element not less than x, upper_bound — strictly greater. But you must be able to write the search by hand — because of the key contest technique below.
Binary search ON THE ANSWER. Often the answer itself is monotone: "can we finish within time t?" — if t works, so does t+1. Then binary search finds the boundary between "impossible" and "possible", and all you write is the check. Example: the integer square root — the largest m such that m² does not exceed n.
Integer square root by binary search on the answer. Enter: 1000000000000
Three classic mistakes:
1. An infinite loop: when searching for the LAST valid value (l = mid), the midpoint must round up: (l + r + 1) / 2. Otherwise the loop hangs at r - l = 1.
2. Midpoint overflow: in other languages write l + (r - l) / 2; in C++ with long long it is usually safe, but keep it in mind.
3. Wrong bounds: the answer must lie within the initial [l, r] — check the extreme values.
Task: there are k printers, each prints a page in t seconds, and you need n pages. What is the minimum time to finish? Solve it with binary search on the answer and the check "how many pages can we print in time T".
Mark the lesson as completed — Level 2 is done!