The dragon explains
Search patterns
The dragon: You've checked lists item by item before. That's called LINEAR SEARCH, and it has a partner pattern worth naming: the flag.
The dragon: A flag starts False, and flips to True the instant you find what you're looking for.
example.pyPython 3party = ["Ember", "Blaze", "Frost"]found = Falsefor name in party: if name == "Blaze": found = Trueprint(found)
OutputTrueThe dragon: Once found becomes True, later items in the loop can't un-find it — the flag only ever moves one direction here.
The dragon: You can track a POSITION the same way — start at -1 (meaning 'not found'), and set it to the real index on a match.
example.pyPython 3party = ["Ember", "Blaze", "Frost"]position = -1for i in range(len(party)): if party[i] == "Frost": position = iprint(position)
Output2The dragon: Now something worth knowing about, even if you won't write it from scratch yet: when a list is SORTED, there's a much faster way to search it.
The dragon: Binary search jumps to the MIDDLE of a sorted list. If the target's bigger, it only searches the top half next; if smaller, only the bottom half. Each check throws away HALF the remaining possibilities.
example.pyPython 3sorted_gold = [10, 25, 40, 55, 70, 85, 100]# checking index 3 (value 55) first# 70 > 55, so only look at [70, 85, 100] next# checking index 5 (value 85)# 70 < 85, so only look at [70] next# checking index 4 (value 70) - found!
The dragon: Same list, same target (70): linear search takes 5 checks (10, 25, 40, 55, 70). Binary search takes just 3 (55, 85, 70) — fewer checks for the exact same answer, because it's sorted.
The dragon: The catch: binary search ONLY works on a sorted list. On an unsorted one, jumping to the middle tells you nothing — linear search is still the right tool there.
Quick check
Check your understanding
Say your answer out loud before reading the marked one. Every wrong option is a mistake real beginners make.
Question 1 of 2
party = ["Ember", "Blaze", "Frost"]. found = False. The loop checks every name but NONE match "Storm". What does found end up as?
question.pyPython 3found = Falsefor name in party: if name == "Storm": found = True
- False — it never gets set to True, since nothing matchedCorrect
- True — the loop finished running, so it must have found something
Why: False. found only changes inside the if block, which only runs on an actual match. If nothing in the list ever equals "Storm", that if body never executes, and found stays False the whole way through — the loop finishing has nothing to do with whether anything was found.
Question 2 of 2
Binary search checks the middle of a sorted list and rules out half the remaining values each time. Would this work on an UNSORTED list?
- No — jumping to the middle only tells you anything useful because the list is in orderCorrect
- Yes — the middle value is still a real value, so the comparison still works
Why: No. Binary search's whole speed advantage comes from the list being SORTED — 'the target is bigger than the middle, so it must be in the second half' is only a safe conclusion when order guarantees it. On an unsorted list, linear search — checking one at a time — is still the only reliable option.
In the game
What you'll practice
Three levels in the game: one guided first try with the shape of the answer already there, then two to solve on your own.
- 1
GuidedYour first try
party = ["Ember", "Blaze", "Frost"]. Check whether "Blaze" is in the party, using a flag: start found = False, and set it to True the moment you spot a match. Print found — should be True.
- +2
PracticeTwo more, on your own
This lesson is part of PRO.
PRO is a one-time $49.99 purchase, no subscription, and unlocks this whole topic along with everything else. Topics 1–3 are free, start to finish.
Unlock this lesson with PROStuck three times? The game offers the answer — unasked.