Lesson 9 Β· Searching πŸ”

Python 3 Β· CCC Junior β€” find things the smart way: scan, generate-and-check, and binary search

The one-sentence version: searching is not one algorithm β€” it is a decision. What is the space? What does ONE candidate look like? How do you check it? And what can you safely throw away? Answer those, and the code writes itself.

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:

9? βœ—4? βœ“ STOP7 β€” never looked at4 β€” never looked at

The first 4 is at index 1 (position 2). Two checks. The second 4 does not matter β€” first means first.

1 Β· THE SPACE
The list itself, in its original order.
2 Β· CANDIDATE + CHECK
One index i β€” valid when values[i] == target.
3 Β· SAFE DISCARD
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.

middle = 11 β€” too small, 14 must be RIGHT of itmiddle of the rest = 17 β€” too big, go LEFT14 βœ“ β€” 3 checks instead of 5
1 Β· THE SPACE
The sorted list β€” but only the part that could still hold the target.
2 Β· CANDIDATE + CHECK
The middle index mid β€” valid when values[mid] == target.
3 Β· SAFE DISCARD
Sorted order! If the middle is too small, EVERYTHING left of it is too small too β€” half the zone is discarded with one comparison.
Keep both shapes in mind. Β§1–§2 are Shape A with bigger clothes (the candidates are not always list items). Β§3–§5 are Shape B: exact match, first-at-least, and searching a space that is not a list at all β€” times.

β˜… 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.

1 Β· What are we searching?

The space: a list? a range of numbers? all substring starts? all times? Name it before touching code.

2 Β· What does ONE candidate look like?

One index, one integer, one start position, one pair of endpoints, one time t. A search is a machine for visiting candidates.

3 Β· What makes it valid?

The check: equals the target? digits all different? slice equals the pattern? at least K copies done?

4 Β· What ORDER do we try them?

Left to right makes the first hit the first occurrence / smallest answer. Order is often the whole point.

5 Β· Why is it SAFE to throw part away?

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)CandidateValid when…
Find the lost ticketone original indexvalue equals the target
Next distinct-digit codeone integer > Xall decimal digits differ
Overlapping messagesone substring startslice equals the pattern
Mirror badgetwo substring endpointsslice equals its reverse
Class handoutsone whole time tat least K handouts completed
The warning that goes with the Recipe: do not reach for binary search just because a problem asks for the smallest answer. Binary search needs the check to flip once β€” false, false, …, true, true. Digit-distinctness flips back and forth (109 βœ“, 110 βœ—, 120 βœ“), so Q2 must be scanned in order. No one-way flip, no binary search.
CONCEPT 1 Β· THE HONEST SCAN

1 Β· Linear Search β€” One by One, Stop at the First

1 Β· THE SPACE
Every index of the list, in original order.
2 Β· CANDIDATE + CHECK
Index i β€” valid when tickets[i] == target. Stop the moment one matches.
3 Β· SAFE DISCARD
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.

CONCEPT 2 Β· GENERATE AND CHECK

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.

1 Β· THE SPACE
Every integer after X: 100, 101, 102, … β€” an endless space, generated one at a time.
2 Β· CANDIDATE + CHECK
One integer β€” valid when all its digits differ: len(set(str(c))) == len(str(c)).
3 Β· SAFE DISCARD
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.

CONCEPT 3 Β· THE HALVING SEARCH

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)

1 Β· THE SPACE
The shrinking zone of indices [left, right] inside a SORTED list.
2 Β· CANDIDATE + CHECK
The middle index mid = (left + right) // 2 β€” valid when values[mid] == target.
3 Β· SAFE DISCARD
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.

CONCEPT 4 Β· BOUNDARY SEARCH

4 Β· First At Least β€” Save It, Then Keep Looking Left

1 Β· THE SPACE
The sorted zone [left, right], same as Β§3.
2 Β· CANDIDATE + CHECK
Midpoint β€” valid when times[mid] >= X (at least, not exactly).
3 Β· SAFE DISCARD
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 searchFirst at least
a[mid] < targetleft = mid + 1left = mid + 1
a[mid] >= targetreturn on equality, else right = mid βˆ’ 1save mid, right = mid βˆ’ 1
duplicatesany match may be returnedthe 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.

CONCEPT 5 Β· EXTENSION

5 Β· Binary Search on the Answer β€” The Space Is Not a List

1 Β· THE SPACE
All whole times t from 0 up to a safe maximum (the fastest printer alone finishing K copies).
2 Β· CANDIDATE + CHECK
One time t β€” valid when enough(t): total copies by t is at least K.
3 Β· SAFE DISCARD
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.

BEFORE YOU CODE

6 Β· Pick the Method β€” And Dodge the Traps

The method picker

What the problem needsUseful method
First match in original, unsorted orderLinear scan from the left (Β§1)
Candidates you can generate, with a checkGenerate and check, in order (Β§2)
Many exact lookups in ascending dataBinary search (Β§3)
First sorted value at least XBoundary search, or bisect_left (Β§4)
Smallest answer with one-way feasibilityBinary search on the answer (Β§5)
Reachable cells or statesBFS / DFS β€” a later lesson (Lesson 8's search was this family)

The trap cards

πŸ—‚οΈ Sorting the tickets. The question asks for a position in the ORIGINAL order. Sort and every position changes β€” a perfectly searched wrong answer.
πŸ” Forgetting the break. No break + overwrite = you report the LAST match. First-occurrence problems are won or lost on that one word.
πŸ“ left < right in exact search. With inclusive bounds, left == right is a real candidate. Use <=, and move PAST mid (Β±1) or the loop may never end.
🧦 str.count misses overlaps. "AA" starts 3 times in "AAAA" (positions 0, 1, 2) β€” but "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).
🎯 Saving nothing in first-at-least. Returning the first valid mid you see gives A valid answer, not the FIRST one. Save it and continue left.
❓ Index, position, value, or count? Four different outputs that all feel like "the answer". Read the problem's output line twice before coding β€” Lesson 9 problems use all four.
Exit ticket (from your teacher's notes): explain in one sentence each β€” (1) why is 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.