0 Β· Start Simple β Two Tiny Searches First
Small lists, plain words. Two shapes of search: walk through everything (this section), or β if the list is sorted β keep cutting the zone in half (Β§3).
Tiny Search A β Find the first 4 π
In [9, 4, 7, 4], where is the first 4? Just look at each value in order and stop when one matches:
The first 4 is at index 1 (position 2). Two checks. The second 4 does not matter β first means first.
The list itself, in its original order.
One index
i β valid when values[i] == target.Nothing is thrown away in bulk β you just stop early. Everything before the match is checked and crossed off, one at a time.
Tiny Search B β The halving game π―
The list [2, 5, 8, 11, 14, 17, 20] is sorted. Find 14 without scanning: look at the middle first.
The sorted list β but only the part that could still hold the target.
The middle index
mid β valid when values[mid] == target.Sorted order! If the middle is too small, EVERYTHING left of it is too small too β half the zone is discarded with one comparison.
β The Search Recipe β Five Questions Before Any Code
From your teacher's success check. If you can answer all five out loud, you understand the search β the code is the easy part.
The space: a list? a range of numbers? all substring starts? all times? Name it before touching code.
One index, one integer, one start position, one pair of endpoints, one time t. A search is a machine for visiting candidates.
The check: equals the target? digits all different? slice equals the pattern? at least K copies done?
Left to right makes the first hit the first occurrence / smallest answer. Order is often the whole point.
The binary-search question. Sorted order, or a one-way (monotonic) check, is the licence. No licence = no discarding β scan honestly.
| Task (from this lesson) | Candidate | Valid when⦠|
|---|---|---|
| Find the lost ticket | one original index | value equals the target |
| Next distinct-digit code | one integer > X | all decimal digits differ |
| Overlapping messages | one substring start | slice equals the pattern |
| Mirror badge | two substring endpoints | slice equals its reverse |
| Class handouts | one whole time t | at least K handouts completed |
1 Β· Linear Search β One by One, Stop at the First
Every index of the list, in original order.
Index
i β valid when tickets[i] == target. Stop the moment one matches.Only the checked prefix is discarded β one cell at a time. The licence is not speed; it is order: left-to-right + stop = FIRST occurrence.
The code (function version)
def linear_search(values, target):
for i in range(len(values)):
if values[i] == target:
return i # first match wins
return -1 # scanned all: absent
index = linear_search([41, 18, 23, 18], 18)
print(index + 1) # position 2
What to remember
β’ Worst case is N checks (target last, or not there at all). Extra memory: O(1).
β’ The function returns a 0-based index; add 1 only when the problem asks for a position β and only when the index is not β1.
β’ Never sort first when the question is about original positions β sorting moves everything and the answer becomes meaningless.
βοΈ Predict: same tickets, target 90 β how many checks, what position?
5 checks, position 5. 41 β, 18 β, 23 β, 18 β, 90 β. And target 3? All 6 checks, answer β1 β absence costs a full scan.
2 Β· Candidates Are Not Always in a List
Sometimes the space is a list. Sometimes you manufacture the candidates yourself β numbers, starts, endpoints, times β and run a check on each.
Every integer after X: 100, 101, 102, β¦ β an endless space, generated one at a time.
One integer β valid when all its digits differ:
len(set(str(c))) == len(str(c)).Each failed candidate is discarded forever β it can never become valid later in the scan. But nothing is discarded in bulk: the check is not one-way, so no halves may be skipped.
The code (generate and check)
candidate = x + 1
while len(set(str(candidate))) != len(str(candidate)):
candidate += 1
print(candidate)
Two things this example teaches
β’ Order is the guarantee. Candidates are tried smallest-first, so the first valid one is automatically the smallest answer β no comparing needed afterwards.
β’ Not one-way β no binary search. Distinctness along the number line goes β β β β β¦ (102 β, 110 β, 120 β). Where would you cut? Any half you throw away might hold the answer. Scan.
βοΈ Predict: X = 109 β what is the next distinct-digit number?
120. Every number 110β119 starts with two 1s (repeated digit), so all fail; 120 has digits 1, 2, 0 β all different.
3 Β· Binary Search β Throw Half Away, Safely
Sorted values [3, 8, 12, 17, 25, 31, 40]. The zone [left, right] always contains every index that could still hold the target β that promise is called the invariant, and each probe keeps it true while halving the zone.
Walk 1 β find 31 (it is there)
Walk 2 β find 20 (it is NOT there)
The shrinking zone of indices [left, right] inside a SORTED list.
The middle index
mid = (left + right) // 2 β valid when values[mid] == target.Sorted order is the licence: if
values[mid] < target, every index up to mid is too small; if bigger, every index from mid on is too big. Half (or more) dies per probe.The code (exact-match template)
def binary_search(values, target):
left = 0
right = len(values) - 1
while left <= right:
mid = (left + right) // 2
if values[mid] == target:
return mid
elif values[mid] < target:
left = mid + 1 # mid is too small: skip past it
else:
right = mid - 1 # mid is too big: skip before it
return -1
Why the details matter
β’ left <= right, not < β when left == right, one candidate remains and it still needs checking.
β’ Move past mid (mid + 1 / mid β 1): mid itself has been ruled out. Forgetting the Β±1 can loop forever.
β’ Cost: at most βlogβ Nβ + 1 probes β 10 for 1,000 values, 20 for a million. Compare linear's million.
βοΈ Predict: find 8 in the same list β which probes, and what answer?
2 probes. mid = 3 β 17 is too big, right = 2. mid = (0+2)//2 = 1 β values[1] = 8 β β return index 1.
4 Β· First At Least β Save It, Then Keep Looking Left
The sorted zone [left, right], same as Β§3.
Midpoint β valid when
times[mid] >= X (at least, not exactly).A valid mid is saved, not returned β then the right side is discarded because anything later is worse (a later shuttle). A too-early mid discards the left as usual.
The code (first-at-least template)
def first_at_least(values, target):
left = 0
right = len(values) - 1
answer = -1
while left <= right:
mid = (left + right) // 2
if values[mid] >= target:
answer = mid # it works β save it
right = mid - 1 # ...but look for an earlier one
else:
left = mid + 1
return answer
Exact vs first-at-least
| Exact search | First at least | |
|---|---|---|
| a[mid] < target | left = mid + 1 | left = mid + 1 |
| a[mid] >= target | return on equality, else right = mid β 1 | save mid, right = mid β 1 |
| duplicates | any match may be returned | the first qualifying index |
Python's built-in for this is bisect_left(a, x) β the first index whose value is >= x. Learn the manual template first; use bisect once you can trace it.
βοΈ Predict: same shuttles β you arrive at 501. And at 601?
501 β the 540 shuttle (500 is too early; 540 is the first that is at least 501). 601 β β1: no departure is at least 601 β the saved answer never gets set.
5 Β· Binary Search on the Answer β The Space Is Not a List
All whole times t from 0 up to a safe maximum (the fastest printer alone finishing K copies).
One time t β valid when
enough(t): total copies by t is at least K.If t fails, every earlier time fails too (fewer minutes can only mean fewer copies) β discard the left. If t works, it might be the FIRST working time β keep it: right = mid.
The code (answer-search template)
left = 0
right = min(speeds) * k # fastest printer alone is enough
while left < right:
mid = (left + right) // 2
copies = sum(mid // a for a in speeds)
if copies >= k:
right = mid # keep a possible answer
else:
left = mid + 1
print(left)
Spot the differences
β’ Loop condition is left < right and there is no return inside β the answer is where the zone closes.
β’ A working mid is kept (right = mid); a failing mid is discarded with everything before it.
β’ Before coding one of these, say the monotonic sentence out loud: "if t works, every later t works." If you cannot say it truthfully, it is not this template.
βοΈ Predict: printers [2, 3], K = 3 β smallest t?
t = 4. copies(4) = 2 + 1 = 3 β; copies(3) = 1 + 1 = 2 β. So the first working time is 4.
6 Β· Pick the Method β And Dodge the Traps
The method picker
| What the problem needs | Useful method |
|---|---|
| First match in original, unsorted order | Linear scan from the left (Β§1) |
| Candidates you can generate, with a check | Generate and check, in order (Β§2) |
| Many exact lookups in ascending data | Binary search (Β§3) |
| First sorted value at least X | Boundary search, or bisect_left (Β§4) |
| Smallest answer with one-way feasibility | Binary search on the answer (Β§5) |
| Reachable cells or states | BFS / DFS β a later lesson (Lesson 8's search was this family) |
The trap cards
<=, and move PAST mid (Β±1) or the loop may never end."AAAA".count("AA") says 2, because it never overlaps. Slide one step at a time and include the last legal start: range(len(text) - len(pattern) + 1).left = mid + 1 safe when values[mid] < target? (2) why does first-at-least keep searching left after finding a valid midpoint? If you can say both, you are ready for the practice page.