Loading
Loading
Halve the search space using a yes/no question that flips exactly once.
Any space that can be divided by a predicate which is false up to some point and true from then on can be searched in logarithmic time. This is much broader than looking up a value in a sorted array: the search space is often the range of possible answers, and the predicate is "is this answer feasible?".
Do not think about values; think about a predicate over positions that reads F F F T T T. Binary search finds the boundary. Every problem below is that same boundary hunt in disguise.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def first_true(lo, hi, predicate): """ Smallest x in [lo, hi] with predicate(x) true, assuming the pattern F F F T T T. Returns hi + 1 when nothing satisfies it. The half-open invariant is what keeps this correct: the answer is always inside [lo, hi], and the loop shrinks that interval without ever excluding it. """ while lo < hi: # Floor division biases toward lo, which is what keeps the loop # terminating when hi == lo + 1. mid = lo + (hi - lo) // 2 if predicate(mid): hi = mid # mid might be the answer: keep it else: lo = mid + 1 # mid is definitely not: discard it return lo def search_on_answer(low, high, feasible): """Binary search the answer space rather than the input.""" best = -1 while low <= high: mid = low + (high - low) // 2 if feasible(mid): best = mid high = mid - 1 # look for something smaller else: low = mid + 1 return best| Status | Problem | Difficulty | Role |
|---|---|---|---|
| First Failing Build#32 | Easy | Primary | |
| Insertion Slot#33 | Easy | Primary | |
| Rotated Catalogue Search#34 | Medium | Primary | |
| Minimum Throughput#35 | Medium | Primary | |
| First and Last Occurrence#36 | Medium | Primary | |
| Longest Rising Streak of Readings#59 | Medium | Related | |
| Sorted Ledger Lookup#96 | Easy | Related | |
| Integer Floor Root#130 | Medium | Primary | |
| Summit Marker#138 | Easy | Primary | |
| Missing Heartbeat#139 | Easy | Primary | |
| Sensor Spacing#140 | Medium | Primary | |
| Fairest Shift Split#141 | Hard | Primary |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign in