What you'll learn
Finding a value is one of the most common things you'll do with data. On an unsorted list you have no choice but to look at everything — O(n). But if the data is sorted, a completely different strategy searches a million items in about 20 steps.
By the end you'll be able to:
- Write a linear search and know when it's the only option
- Explain how binary search halves the problem each step
- Show why binary search is
O(log n)and needs sorted input
Linear search
The simplest search: check each element from the start until you find the target or run out. It works on any list, sorted or not, but in the worst case it inspects all n elements — O(n). For unsorted data, there's nothing faster.
Binary search
On a sorted array you can be far smarter. Look at the middle element: if it's the target, done. If the target is larger, it must be in the right half; if smaller, the left half. Either way you throw away half the remaining elements with one comparison. Watch it find 23:
Key idea
n → n/2 → n/4 → …, reaching 1 in about log₂(n) steps. A sorted array of a million items needs only ~20 comparisons.In code
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid # found
elif arr[mid] < target:
lo = mid + 1 # discard the left half
else:
hi = mid - 1 # discard the right half
return -1 # not foundWatch out
O(n log n)) so every later search is O(log n) — or reach for a hash table (Module 14) for O(1) average lookups.Complexity
| Search | Requires | Time | Space |
|---|---|---|---|
Linear | Nothing | O(n) | O(1) |
Binary (iterative) | Sorted array | O(log n) | O(1) |
Binary (recursive) | Sorted array | O(log n) | O(log n) call stack |
Hash lookup | Hash table | O(1) average | O(n) |
Recap & quick check
Key takeaways
- Linear search checks each element — O(n), works on any data.
- Binary search needs a sorted array and halves the range each step: O(log n).
- Compare with the middle, then keep only the half that can contain the target.
- A million sorted items take about 20 comparisons.
- Repeated searching? Sort once (O(n log n)) or use a hash table for O(1) average.
Quick check
1. What must be true to use binary search?
2. Binary search on n elements is:
3. If arr[mid] < target, binary search next looks in:
4. About how many comparisons to binary-search 1,000,000 sorted items?
Binary search is the payoff for keeping data sorted — which is exactly what the next five modules do. Next up: Module 10 — Elementary Sorts.