Pythonoid

CurriculumAlgorithmic Thinking in Python, for KidsSearch patterns

Linear Search vs Binary Search in Python, Explained

Checking one item at a time has a name — and a smarter option exists when the list is sorted.

Lesson 2 of 4PROAges 10+
See what PRO unlocks →

Search patterns

You've checked lists item by item before. That's called LINEAR SEARCH, and it has a partner pattern worth naming: the flag.

A flag starts False, and flips to True the instant you find what you're looking for.

party = ["Ember", "Blaze", "Frost"]
found = False
for name in party:
    if name == "Blaze":
        found = True
print(found)

Output

True

Once found becomes True, later items in the loop can't un-find it — the flag only ever moves one direction here.

You can track a POSITION the same way — start at -1 (meaning 'not found'), and set it to the real index on a match.

party = ["Ember", "Blaze", "Frost"]
position = -1
for i in range(len(party)):
    if party[i] == "Frost":
        position = i
print(position)

Output

2

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.

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.

sorted_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!

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 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.

Check your understanding

party = ["Ember", "Blaze", "Frost"]. found = False. The loop checks every name but NONE match "Storm". What does found end up as?

found = False
for name in party:
    if name == "Storm":
        found = True
  • False — it never gets set to True, since nothing matched
  • 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.

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 order
  • 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.

What you'll practice

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.

Unlock this lesson with PRO →

More from this topic

Search patterns is one lesson inside Algorithmic Thinking in Python, for Kids — see the full lesson order and what the whole topic covers.

View the full topic →