Unit 27: Searching
Finding things, slowly and quickly.
Unit 27 of 31 in Python for kids. Its 5 lessons are One at a Time, Counting the Cost, Splitting in Half, Why Halving Wins and Search Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🔎 One at a Time
The obvious way
Linear search checks each item in turn until it finds what it wants. Simple, and it works on anything — sorted or not.
Python
def find(items, wanted):
for item in items:
if item == wanted:
return True
return False
print(find([4, 9, 2], 9))
print(find([4, 9, 2], 7))It prints
True False
Where is it, not just whether
Usually you want the position. enumerate gives you the index as you go, and -1 is the usual way of saying "not here".
Python
def position(items, wanted):
for i, item in enumerate(items):
if item == wanted:
return i
return -1
print(position(["cat", "dog", "hen"], "dog"))
print(position(["cat", "dog", "hen"], "cow"))It prints
1 -1
Python already has both
in and .index() are linear search, written for you. Write your own to understand it; use Python's in real code — except that .index() raises ValueError when nothing matches.
Python
pets = ["cat", "dog"]
print("dog" in pets)
print(pets.index("dog"))
try:
pets.index("cow")
except ValueError:
print("not in the list")It prints
True 1 not in the list
Try it yourself
Why return -1 rather than 0 when nothing is found?
- 0 is faster
- 0 is a real position — the first one — so it would look like a match
- It has to be negative
- There is no reason
What does this print?
Python
def position(items, wanted):
for i, item in enumerate(items):
if item == wanted:
return i
return -1
print(position([5, 3, 5], 5))Answer them in the app
⏱️ Counting the Cost
How much work is it really?
Count the comparisons instead of guessing. Finding something near the front is quick; finding the last item means checking every single one.
Python
def steps_to_find(items, wanted):
steps = 0
for item in items:
steps = steps + 1
if item == wanted:
return steps
return steps
numbers = list(range(1, 101))
print(steps_to_find(numbers, 1))
print(steps_to_find(numbers, 100))It prints
1 100
The worst case is what counts
A list twice as long takes twice as long to search. Programmers call this O(n) — the work grows in step with the number of items.
Python
def steps(n):
return n
print(steps(10))
print(steps(100))
print(steps(1000))It prints
10 100 1000
Searching things that are not numbers
Linear search works on anything you can compare. Here it looks through a list of dictionaries for the right name.
Python
people = [
{"name": "Ada", "age": 9},
{"name": "Sam", "age": 11},
]
def find_person(people, name):
for person in people:
if person["name"] == name:
return person["age"]
return None
print(find_person(people, "Sam"))
print(find_person(people, "Kim"))It prints
11 None
Try it yourself
A linear search of 500 names takes at most how many comparisons?
- 1
- About 9
- 250
- 500
Answer it in the app
✂️ Splitting in Half
The way you look up a name in a phone book
You do not start at page one. You open the middle, see which half the name is in, and throw the other half away. That is binary search — the same halving a binary search tree does, on a plain list.
Python
numbers = [1, 3, 5, 7, 9, 11]
low = 0
high = len(numbers) - 1
middle = (low + high) // 2
print(middle)
print(numbers[middle])It prints
2 5
The whole algorithm
Keep two markers for the part still worth looking at. Check the middle; if it is too small move low up, if too big move high down. Stop when they cross.
Python
def binary_search(items, wanted):
low = 0
high = len(items) - 1
while low <= high:
middle = (low + high) // 2
if items[middle] == wanted:
return middle
if items[middle] < wanted:
low = middle + 1
else:
high = middle - 1
return -1
numbers = [1, 3, 5, 7, 9]
print(binary_search(numbers, 9))
print(binary_search(numbers, 4))It prints
4 -1
It only works on sorted data
This is the catch. Binary search decides which half to keep by comparing — and on an unsorted list that decision is meaningless, so it will happily miss something that is right there.
Python
def binary_search(items, wanted):
low = 0
high = len(items) - 1
while low <= high:
middle = (low + high) // 2
if items[middle] == wanted:
return middle
if items[middle] < wanted:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([9, 1, 5, 3], 9))
print(binary_search(sorted([9, 1, 5, 3]), 9))It prints
-1 3
Try it yourself
Why must low become middle + 1 rather than middle?
- To make it faster
- The middle has already been checked, and leaving it in would loop for ever
- It does not matter
- To avoid going past the end
What does this print?
Python
items = [2, 4, 6, 8]
low = 0
high = 3
middle = (low + high) // 2
print(middle, items[middle])Answer them in the app
📉 Why Halving Wins
Watch the difference
Same list, same target, both searches counted. This is the whole unit in one output.
Python
numbers = list(range(1, 101))
def linear_steps(items, wanted):
steps = 0
for item in items:
steps = steps + 1
if item == wanted:
return steps
return steps
def binary_steps(items, wanted):
steps = 0
low = 0
high = len(items) - 1
while low <= high:
steps = steps + 1
middle = (low + high) // 2
if items[middle] == wanted:
return steps
if items[middle] < wanted:
low = middle + 1
else:
high = middle - 1
return steps
print(linear_steps(numbers, 100))
print(binary_steps(numbers, 100))It prints
100 7
Doubling the list adds one step
Halving means the list has to *double* before the search needs one more step. Programmers call this O(log n) — and it is why a million items still only take about twenty.
Python
sizes = [10, 100, 1000, 1000000]
for size in sizes:
steps = 0
remaining = size
while remaining > 0:
steps = steps + 1
remaining = remaining // 2
print(size, steps)It prints
10 4 100 7 1000 10 1000000 20
The recursive version
Binary search says "search this smaller part", which is a recursive idea. The base case is running out of list.
Python
def search(items, wanted, low, high):
if low > high:
return -1
middle = (low + high) // 2
if items[middle] == wanted:
return middle
if items[middle] < wanted:
return search(items, wanted, middle + 1, high)
return search(items, wanted, low, middle - 1)
numbers = [1, 3, 5, 7, 9]
print(search(numbers, 7, 0, len(numbers) - 1))It prints
3
Python has it built in
The bisect module does binary search properly. bisect_left gives the position where a value is, or where it *would* go — handy for keeping a list sorted as you add to it.
Python
from bisect import bisect_left, insort
numbers = [1, 3, 5, 7]
print(bisect_left(numbers, 5))
print(bisect_left(numbers, 4))
insort(numbers, 4)
print(numbers)It prints
2 2 [1, 3, 4, 5, 7]
Try it yourself
You must search a list once, and it is not sorted. What is usually best?
- Sort it first, then binary search
- Linear search — sorting costs more than the one search saves
- Binary search on the unsorted list
- Neither will work
Answer it in the app
🏆 Search Master
Try it yourself
What does this print?
Python
items = [1, 2, 3, 4, 5, 6, 7]
low = 0
high = 6
middle = (low + high) // 2
low = middle + 1
middle = (low + high) // 2
print(items[middle])Answer it in the app