Binary Search
Loading
Loading
Binary Search
Lower and upper bounds, and the trick of binary searching a space that is not the input.
By the end of this chapter
| Bound | Predicate | Returns |
|---|---|---|
| Lower bound | value ≥ target | First index not less than the target |
| Upper bound | value > target | First index strictly greater |
The count of a value is upper bound minus lower bound, and the last occurrence is upper bound minus one. If the two bounds are equal, the value is absent — so no separate existence check is needed.
Sometimes there is no sorted array at all. What is sorted is the set of candidate answers: some are infeasible, the rest are feasible, and there is one flip between them.
def minimum_feasible(low, high, feasible): while low < high: mid = low + (high - low) // 2 if feasible(mid): high = mid else: low = mid + 1 return lowCan you recognise the pattern?
A problem asking for the smallest or largest value that satisfies some condition, where testing one candidate is cheap.
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 4 practice problems.