Searching algorithms
| English | Chinese | Pinyin |
|---|---|---|
| search | 搜索 | sōu suǒ |
| binary search | 二分查找 | èr fēn chá zhǎo |
| linear search | 线性查找 | xiàn xìng chá zhǎo |
Finding the needle
- 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.
Linear search checks every letter in turn until W is found
Searching algorithms
binary halves the range each step
Linear search checks every item; binary halves a sorted list — far fewer comparisons.
A linear search:
Linear search needs no preparation and works on any list, at worst O(n).
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.
Searching a sorted list, like a phone book, is far faster than checking every entry.
Match each search to its key facts.
Binary search is far faster (O(log n)) but only on sorted data; linear works anywhere at O(n).
The worst-case time complexity of binary search is:
Halving the range each step gives a logarithmic number of comparisons.
About how many comparisons does a binary search need for one million sorted items?
$\log_2(1\,000\,000) \approx 20$ — about 20 comparisons.
Linear vs binary search
Worked example. A linear search checks items one by one (fine for small or unsorted lists). A binary search halves a sorted list each step — finding an item among a million in about 20 checks.
- Abstract Data Types include the dictionary (key→value) and the graph; Big O notation describes how running time grows.
You've got it
- 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