Search concepts
Linear search scans every element — O(n). Binary search halves the search space each step — O(log n). The catch is that binary search only works on sorted data.
- Describe how linear search works and state its complexity
- Describe how binary search works and why it requires sorted data
- Compare O(n) and O(log n) at scale
Searching — finding whether a value exists in a collection, and where — is one of the most common operations in programming. There are two fundamental algorithms for searching a list, and the difference between them is dramatic.
Linear search — O(n)
Linear search checks each element in order: first, second, third, and so on until either the target is found or the end of the list is reached. In the worst case (target is last, or absent) it examines every element — O(n).
No assumption about the data is needed. The list can be in any order; linear search works regardless.
Searching [4, 8, 2, 9, 1, 6] for 9:
Check 4. Not it.
Check 8. Not it.
Check 2. Not it.
Check 9. Found at index 3.At n=1 000 000, worst-case linear search examines 1 000 000 elements.
Binary search — O(log n)
Binary search exploits a sorted list. At each step it compares the target to the middle element:
- If the target equals the middle, done.
- If the target is smaller, the right half is impossible — discard it.
- If the target is larger, the left half is impossible — discard it.
Each comparison halves the remaining search space. A list of 1 000 000 elements is reduced to 500 000, then 250 000, then 125 000 … twenty comparisons later you have either found the target or proved it absent. That is O(log n): the number of steps grows logarithmically with n.
Searching [1, 2, 4, 6, 8, 9] for 9:
Middle index 2 → value 4. Target (9) is larger. Discard left half.
Remaining: [6, 8, 9]. Middle index 1 → value 8. Target larger. Discard left.
Remaining: [9]. Middle index 0 → value 9. Found.The catch: sorted data only
Binary search is correct only on sorted data. If the list is unsorted, discarding a half based on the middle element may throw away the target entirely.
The analogy: imagine looking up a word in a dictionary by opening to the middle, checking whether your word comes before or after, and repeating. That works precisely because the pages are in alphabetical order. Opening a random book (no order) the same way would be nonsense.
Sorting costs O(n log n). If you sort before searching, the combined cost is O(n log n) — worthwhile only if you will search many times. For a single search on unsorted data, linear scan at O(n) is better.
Complexity comparison
| n | O(n) steps | O(log n) steps |
|---|---|---|
| 100 | 100 | 7 |
| 10 000 | 10 000 | 14 |
| 1 000 000 | 1 000 000 | 20 |
| 1 000 000 000 | 1 000 000 000 | 30 |
The logarithm grows so slowly that binary search on a billion sorted elements takes about 30 comparisons. Linear search on the same data takes up to a billion.
O(log n) is pronounced "log n." For practical purposes, think of it as "the number of times you can halve n before it reaches 1." Halving 1 000 000 twenty times gives roughly 1. So log₂(1 000 000) ≈ 20.
Where to go next
Next: search in Python — implementing both algorithms and running a test that shows binary search failing on unsorted input.
Recursion in Python
Implement factorial and Fibonacci recursively, add print traces to see the call sequence, and learn about Python's recursion limit.
Search in Python
Implement linear search and iterative binary search, then watch binary search fail on unsorted input to understand why sorted data is a hard requirement.