Chapter 7 · Search and sort¶
Binary search is not one template. Decide what the final position means before choosing boundaries.
Three binary-search families¶
| Family | Search interval | Result |
|---|---|---|
| exact match | inclusive [lo, hi] |
matching index or -1 |
| first true | half-open [lo, hi) |
first position satisfying predicate |
| answer space | known bounded candidates | smallest feasible value |
flowchart TD
accTitle: Choosing one of the three binary-search contracts
accDescr: Use exact-match search when looking for a target stored in sorted data, first-true search when locating a monotone boundary, and answer-space search when candidates are ordered and a monotone feasibility test can identify the smallest feasible answer.
A{"What does the returned<br/>position mean?"}
A -->|"index containing target"| B["Exact match"]
B --> C["Inclusive [lo, hi]<br/>return index or -1"]
A -->|"first position where<br/>a property becomes true"| D["Boundary / first true"]
D --> E["Half-open [lo, hi)<br/>return lo, possibly n"]
A -->|"smallest numeric answer<br/>that can work"| F{"Is feasibility<br/>monotone?"}
F -->|yes| G["Binary search on answer"]
G --> H["Known lower bound +<br/>known feasible upper bound"]
F -->|no| I["Binary search is invalid:<br/>change the model"]All three repeatedly discard half of an ordered candidate set, but they cannot share boundaries blindly because their return contracts differ.
Exact match¶
Invariant: if the target exists, it remains inside the inclusive search interval.
def binary_search(values: Sequence[T], target: T) -> int:
"""Return any index containing ``target``, or ``-1`` when absent."""
# Invariant: a present target remains inside inclusive [low, high].
low, high = 0, len(values) - 1
while low <= high:
middle = low + (high - low) // 2
if values[middle] == target:
return middle
if values[middle] < target:
# middle and everything left of it are too small.
low = middle + 1
else:
# middle and everything right of it are too large.
high = middle - 1
return -1
inline int binary_search_index(
const std::vector<int>& values, int target) {
// Invariant: a present target remains inside inclusive [low, high].
int low = 0;
int high = static_cast<int>(values.size()) - 1;
while (low <= high) {
const int middle = low + (high - low) / 2;
if (values[middle] == target) {
return middle;
}
if (values[middle] < target) {
// middle and everything left of it are too small.
low = middle + 1;
} else {
// middle and everything right of it are too large.
high = middle - 1;
}
}
return -1;
}
inline int binary_search_index(
const std::vector<int>& values, int target) {
// Invariant: a present target remains inside inclusive [low, high].
int low = 0;
int high = static_cast<int>(values.size()) - 1;
while (low <= high) {
const int middle = low + (high - low) / 2;
if (values[middle] == target) {
return middle;
}
if (values[middle] < target) {
// middle and everything left of it are too small.
low = middle + 1;
} else {
// middle and everything right of it are too large.
high = middle - 1;
}
}
return -1;
}
First true¶
The predicate must be monotone:
Invariant: every position before lo is false, and the first true position
remains in [lo, hi). Returning n is meaningful: no position is true.
def first_true(size: int, predicate: Callable[[int], bool]) -> int:
"""Return the first true index in ``[0, size)``, or ``size``."""
if size < 0:
raise ValueError("size must be nonnegative")
# [low, high) always contains the first true position or sentinel size.
low, high = 0, size
while low < high:
middle = low + (high - low) // 2
if predicate(middle):
# middle may be the answer, so keep it.
high = middle
else:
# middle is false; discard the false prefix through middle.
low = middle + 1
return low
template <class Predicate>
int first_true(int size, Predicate predicate) {
if (size < 0) {
throw std::invalid_argument("size must be nonnegative");
}
// [low, high) contains the first true position or sentinel size.
int low = 0;
int high = size;
while (low < high) {
const int middle = low + (high - low) / 2;
if (predicate(middle)) {
// middle may be the answer, so keep it.
high = middle;
} else {
// middle is false; discard the false prefix through middle.
low = middle + 1;
}
}
return low;
}
template <class Predicate>
int first_true(int size, Predicate predicate) {
if (size < 0) {
throw std::invalid_argument("size must be nonnegative");
}
// [low, high) contains the first true position or sentinel size.
int low = 0;
int high = size;
while (low < high) {
const int middle = low + (high - low) / 2;
if (predicate(middle)) {
// middle may be the answer, so keep it.
high = middle;
} else {
// middle is false; discard the false prefix through middle.
low = middle + 1;
}
}
return low;
}
Binary search on the answer¶
Use this when:
- the answer is numeric or ordered;
- you can test feasibility for a candidate;
- feasibility changes monotonically;
- you know an inclusive range containing at least one feasible candidate.
Write and test the feasibility function separately. Its complexity multiplies the logarithmic search count.
Sorting as a structural transformation¶
Sorting is useful when order makes candidate elimination provable: merge intervals, two pointers, sweep lines, greedy scheduling, and adjacency-based duplicate skipping. Record whether sorting mutates input and whether original indices must be retained.
Practice ladder · write the search contract¶
| Rung | Problem | Thinking prompt |
|---|---|---|
| 1 | Binary Search | What exactly means “not found”? |
| 2 | Find First and Last Position | Which two monotone boundaries define the answer? |
| 3 | Search in Rotated Sorted Array | Which half is provably sorted this iteration? |
| 4 | Koko Eating Bananas | Why does feasibility stay true above the boundary? |
State the interval style and final return meaning before calculating a midpoint.