探索アルゴリズム

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
    ENDIF
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

Binary search

low ← 1 ;  high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    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.

Worked example: trace a binary search

Choosing between them

• 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

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.

Marks that slip away

You've got it