Search with an invariant
Use sorted order to discard impossible answers without losing the right one.
BY THE END, YOU CAN
- Explain binary search's sorted-input requirement
- Maintain a half-open search interval
- Handle missing values and duplicates deliberately
Diagram description: 3, 8, 12, 19, 27, 31, 44, 50; target 19 is still possible here: 0–3; 0: lo; 2: mid: 12 < 19; 4: hi (excluded)
Order buys information
A linear search checks items until it finds a match or reaches the end.
Binary search uses sorted order: compare the middle value, then discard a half that cannot contain the answer. The number of comparisons grows logarithmically, but only because the ordering assumption is true. Sorting solely for one lookup may cost more than scanning once.
Binary search is compelling when data is already sorted or many searches reuse the order. Identify the cost of maintaining that order as new records arrive.
Make the interval precise
An implementation is easier to reason about when its candidate region is defined precisely.
With a half-open interval [lo, hi), lo is included and hi is excluded, so the region is empty when lo equals hi. The loop runs while lo < hi: if the middle value is too small, set lo = mid + 1; otherwise set hi = mid. Each iteration must shrink the region while preserving the possibility of a valid answer.
Python's bisect_left returns the insertion position before existing equal values. It does not promise that a matching value exists. Check the returned index against the collection length and compare the element before claiming a successful lookup.
from bisect import bisect_left
ids = [10, 20, 20, 40]
i = bisect_left(ids, 20)
found = i < len(ids) and ids[i] == 20
print(i, found)Search is a design decision
The desired answer changes the algorithm.
Do you want any matching ID, the first duplicate, every duplicate, or the next scheduled time after a threshold? Spell out that contract before choosing code. Test an empty collection, a target before the first element, a target after the last, and duplicates.
In Relay, a sorted schedule could find the first future job efficiently, but inserting into a Python list still moves elements. A fast search does not make the entire data structure fast.
COMMON FAILURE MODE
Treating an insertion position as proof of a match, or ignoring the O(n) insertion cost of a sorted Python list.
TRY IT YOURSELF
For [2, 5, 5, 9], predict bisect_left positions for 1, 5, 8, and 10. Identify which positions represent actual matches.
Make the call in the laboratory.
The two-question checkpoint, your notes, and your saved progress are in the laboratory. Free, with no account.
Open in the laboratory ↗CONNECT IT TO RELAY
Implement a lookup for scheduled Relay jobs and write down whether it returns a job, an insertion point, or both.