Search Strategies
Linear search checks everything, one item at a time. Binary search eliminates half the remaining possibilities on every step — but only works on sorted data.
By the end of this lesson, you can
- Explain the difference between linear search and binary search, and what each requires of its input
- Trace both strategies searching for a target value, counting the comparisons each makes
- Explain why binary search only works correctly on sorted data
Why it matters
Finding a value in a collection is one of the most common problems in programming, and there’s more than one reasonable way to do it. Two strategies with very different trade-offs — checking everything versus eliminating half the possibilities at a time — cover most of what comes up, and knowing when each applies avoids reaching for the wrong one.
Mental model
- Linear search checks items one at a time, from the start, until it finds the target or runs out of items. It works on any collection, in any order.
- Binary search only works on sorted data. It checks the middle item; if that’s not the target, the comparison alone reveals which half the target must be in (if it’s there at all) — so the other half is eliminated entirely, without ever checking it.
def linear_search(numbers, target):
for i in range(len(numbers)):
if numbers[i] == target:
return i
return -1
def binary_search(numbers, target):
low = 0
high = len(numbers) - 1
while low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
return mid
elif numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1(// is integer division — like /, but it rounds down to a whole
number, which is what a middle index needs to be.)
Trace it
Both functions searching the same sorted list, [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], for the target 23:
| Step | low | high | mid | numbers[mid] | What happens |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23 — search the right half only |
| 2 | 5 | 9 | 7 | 56 | 56 > 23 — search the left half of what remains |
| 3 | 5 | 6 | 5 | 23 | Match — found at index 5 |
linear_search finds the same answer by checking indices 0, 1,
2, 3, 4, 5 in order — six comparisons, versus binary search’s
three. The gap between them grows dramatically as the list gets
longer: doubling the list roughly doubles linear search’s worst case,
while binary search only needs one more comparison, because each step
still cuts the remaining possibilities in half.
Check your understanding
Or reveal the answer without checking
Answer:2
low = 0, high = 5 (the last index). mid = (0 + 5) // 2 = 2 (integer division rounds down), pointing at the value 5 — not yet a match, so the search continues into the right half.
Or reveal the answer without checking
Answer:Binary search decides which half to eliminate based on a comparison that only means something if the data is in order
Every step of binary search assumes 'smaller values are to the left, larger to the right' to safely discard half the remaining data. Without that guarantee, the eliminated half might have contained the target all along.
Practice: warm-up
For the sorted list [4, 9, 15, 22, 30, 41, 55], trace linear_search
looking for 41 — write down each index checked, in order — then trace
binary_search looking for the same value, writing down low, high,
and mid at each step.
Stuck? Reveal one hint at a time.
Hint 1
linear_search checks index 0, then 1, then 2, and so on, until it finds a match — just count how many checks that takes for 41.
Hint 2
binary_search starts with low = 0 and high = 6 (the last index) for a 7-item list.
Reveal both traces
Try the problem yourself before reading this. There is often more than one reasonable approach — treat this as one worked example, not the only correct answer.
linear_search: checks indices 0, 1, 2, 3, 4, 5 — six comparisons, found at index 5
binary_search:
step 1: low=0, high=6, mid=3 -> numbers[3]=22, 22 < 41 -> low=4
step 2: low=4, high=6, mid=5 -> numbers[5]=41, match! found at index 5
Three total comparisons for binary_search vs. six for linear_search.Practice: apply it
This code searches a list of usernames that were added in the order
people signed up — not alphabetical order — using binary_search:
usernames = ["linus_t", "grace99", "ada_l", "margaret_h"]
print(binary_search(usernames, "linus_t"))Or reveal the answer without checking
Answer:-1 — usernames isn't sorted, so binary_search's first comparison eliminates the half that actually contains linus_t
binary_search checks the middle first ("ada_l"), decides linus_t must be in the other half based on alphabetical comparison, and eliminates the half where linus_t actually is — since signup order has nothing to do with alphabetical order. It reports a value that is genuinely present as missing.
Modification challenge: fix this by either sorting usernames
first with usernames.sort() before calling binary_search, or by
switching to linear_search, which works correctly regardless of
order.
Summary
- Linear search checks items one at a time and works on any collection, in any order.
- Binary search eliminates half the remaining possibilities on every step, but only works correctly on sorted data.
- The speed gap between them grows as the collection gets larger — binary search needs only one extra comparison each time the collection doubles.
- Running binary search on unsorted data doesn’t raise an error — it can silently report a present value as missing, a logic error rather than a crash.