Loading...
Tier I · Fundamentals
Halving the search space — over arrays, and over the answer itself.
Binary search halves the search space each step, so a range of a billion takes about 30 steps. It only works when the answer has a yes/no boundary: false up to some point, then true from there on.
Sorted array, looking for 72. lo and hi mark the part still in play: all of it.
Each look at the middle throws away half of what is left. Nine elements take three looks, a billion take about thirty.
| C++ | Python | Java | |
|---|---|---|---|
| First position | lower_bound | bisect_left | Arrays.binarySearch |
| First position | upper_bound | bisect_right | none built in |
The search space is sometimes a sorted array. More often it is a numeric answer, such as a capacity, a speed, or a number of days, that you test with a simple feasibility check. "Minimize the maximum" and "maximize the minimum" are both this, and there you write the loop yourself, since the library forms only search arrays.
| Approach | Time |
|---|---|
| Linear scan | |
| Binary search on a sorted array | |
| Binary search on the answer, check | , = answer range |
Use it when the input is sorted, or when you can ask "is this candidate feasible?" and the answer flips exactly once as the candidate grows.
The problems below start with plain sorted-array search, move through rotated and mountain arrays, and end with searching the answer.