Searching algorithms
Searching algorithms
- A search finds a target value in a collection and returns its position (or "not found").
- The two classics are linear and binary search.
- The right choice depends on whether the data is sorted.
Linear search
FOR i ← 1 TO n
IF A[i] = target THEN RETURN i
NEXT i
RETURN -1 // not found
- Walks from start to end, comparing each element.
- Works on any list (no sorting needed); worst case O($n$) (target last or absent).
- Use it on unsorted data or small lists.
Practice
A linear search:
Linear search needs no preparation and works on any list, at worst O(n).
Practice
Linear search is the better choice when the data is:
With no order to exploit (or a tiny list), linear search avoids the cost of sorting first.
Binary search
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN RETURN mid
IF A[mid] < target THEN low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- Needs the data sorted. Check the middle, then search the half that could contain the target — halving the range each step.
- Worst case O($\log_2 n$) — about 20 comparisons for a million items.
Practice
Binary search requires the data to be:
Binary search relies on order to decide which half to discard, so the data must be sorted.
Practice
The worst-case time complexity of binary search is:
Halving the range each step gives a logarithmic number of comparisons.
Practice
About how many comparisons does a binary search need for one million sorted items?
$\log_2(1\,000\,000) \approx 20$ — about 20 comparisons.
You've got it
Key idea
- linear search: any list, no prep, O($n$) — best for unsorted/small data
- binary search: needs sorted data, halves the range, O($\log_2 n$)
- ~20 comparisons find an item among a million (binary) vs up to a million (linear)
- sort first only if you'll search many times