🧠 Algorithms & Problem Solving, lesson 3 of 6
Linear vs binary search
Find items one by one, or halve the search space every step.
10 min
1 exercise
2 quizzes
0/3 solved
Getting Python ready… examples can run in a moment.
Linear search checks items one at a time until it
finds the target. Simple, and it works on any list,
but a million items may need a million checks. Python's
x in my_list and my_list.index(x) work this way.
Linear search with a step counter
Each result is (index, steps). A missing value
costs the most: every item gets checked.
Binary search needs sorted data, but it's dramatically faster. It's the "guess my number, higher or lower?" strategy:
- Look at the middle item
- Target bigger? Discard the left half. Smaller? Discard the right half
- Repeat on what's left
Every step halves the search space, so a million items take at most about 20 steps.
Binary search
Compare the step counts with linear search. Then try
nums = list(range(1_000_000)).
What does this print?
A sorted list has 1,000,000 items. About how many steps does binary search need in the worst case?
bisect: grades from cutoffs
bisect_right counts how many cutoffs are ≤ the
score, which picks the right letter. Try a score of 70.
Implement binary search
Complete binary_search(items, target) for a sorted
list. Return the target's index, or -1 if it's not
there. Use the halving strategy (no in or
.index()): the check counts how many items you look
at!