Searching algorithms
| English | Chinese | Pinyin |
|---|---|---|
| linear search | 线性查找 | xiàn xìng chá zhǎo |
| binary search | 二分查找 | èr fēn chá zhǎo |
Twenty questions for a million names
- A phone book holds a million names. Checking them one at a time, you would expect half a million comparisons before finding the one you want.
- Open it in the middle instead, decide which half the name is in, and throw the other half away. Repeat. You reach any name in twenty comparisons.
- Half a million against twenty is not a small saving; it is the difference between a program that works and one that cannot be used. And it costs one thing: the list must already be in order.
- This lesson is linear search 线性查找 and binary search 二分查找, how each performs, and how to choose.
Linear search
FOR i ← 1 TO n
IF A[i] = target THEN RETURN i
NEXT i
RETURN -1 // not found
- It walks from the start, comparing each element with the target, and stops when it finds a match or reaches the end.
- It works on any list, sorted or not, and on any structure that can be stepped through.
- Worst case: the target is last or absent, so all $n$ elements are compared, which is $O(n)$. On average, about half.
One at a time, from the beginning
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
- It requires the data to be sorted. Compare the middle element with the target: if it matches, stop; if the target is larger, discard the lower half; otherwise discard the upper half.
- Each comparison halves the range still to be searched, so the number of comparisons is $O(\log_2 n)$.
- That is why a million items need about twenty comparisons: $2^{20}$ is just over a million.
Searching algorithms
binary halves the range each step
Linear search checks every item; binary halves a sorted list — far fewer comparisons.
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.
Binary search can be used on any list, sorted or not.
It decides which half to discard by comparing with the middle element, which is only meaningful if the data is in order.
Binary search is O(log n) because each comparison ____ the range still to be searched.
Twenty halvings take a million down to one, which is why 2^20 being just over a million is the number to remember.
Worked example: trace a binary search
- The sorted list is 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Trace the search for 23.
lowis 1,highis 10, somidis 5, holding 16. 16 is less than 23, so discard the lower half:lowbecomes 6.low6,high10, somidis 8, holding 56. 56 is greater than 23, sohighbecomes 7.low6,high7, somidis 6, holding 23. Found, in three comparisons where a linear search would have taken six.- Show
low,high,midand the value at each step. Most of the marks are in the trace, not the answer.
In the sorted list 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, how many comparisons does a binary search need to find 23?
mid 5 holds 16 (too small), mid 8 holds 56 (too large), mid 6 holds 23. A linear search would have taken six.
Choosing between them
| linear | binary | |
|---|---|---|
| data must be sorted | no | yes |
| comparisons, worst case | $n$ | $\log_2 n$ |
| a million items | up to 1,000,000 | about 20 |
| suits | unsorted or small lists, linked lists | large sorted arrays, searched repeatedly |
- Sorting first costs more than one linear search, so binary search pays only when the list is already sorted or will be searched many times.
- Binary search also needs direct access to the middle element, which an array has and a linked list does not.
Worked example: justify the choice
- A program searches an unsorted list of 50 records once. Linear search: sorting the list first would cost far more than the 50 comparisons the search needs.
- A program searches a sorted array of a million records thousands of times a second. Binary search: the data is already sorted and each search costs about 20 comparisons instead of up to a million.
- A program searches a linked list. Linear search: binary search needs to jump straight to the middle element, and a linked list can only be followed from the start.
- Name the algorithm, then the property of the data that decides it.
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).
When is linear search the better choice? Select all that apply.
The last case is exactly where binary search wins. Sorting first costs more than a single linear search, so it pays only over many searches.
The cost of keeping the file sorted
- Binary search is only available on a sorted list, and that sorting is not free. A question that asks you to justify a choice is asking you to price it.
- If the data is searched often and changed rarely, sort it once and every later search is $\log_2 n$. That is the case for a dictionary or a lookup table.
- If the data changes constantly, every insertion has to keep the order, which costs a shift of the later elements. A linear search over unsorted data can then be the cheaper total.
- Numbers make the argument concrete: a million records need up to a million comparisons linearly, but only 20 by binary search, since $2^{20} > 10^6$.
- So the marked answer names both halves: how often it is searched, and how often it changes.
Put the justification for choosing a search algorithm in order.
A justify question wants the trade-off, not the winner. Binary search on a list that changes constantly can cost more in total than a linear search.
Marks that slip away
- Binary search requires sorted data. Saying "it is faster" without that condition loses the mark.
- Each step halves the range, which is where the $\log_2 n$ comes from. Give the reason, not just the notation.
- Both searches must be able to report not found, which is what the
-1and the loop condition are for. - Binary search needs direct access, so it does not apply to a linked list even if the list is sorted.
You've got it
- linear search compares each element from the start, works on any list, and is $O(n)$
- binary search needs sorted data with direct access, compares the middle and halves the range each time, giving $O(\log_2 n)$: about 20 comparisons for a million items
- trace a binary search by showing
low,high,midand the value at each step - choose from the data: unsorted, small or a linked list means linear; large, sorted and searched often means binary