Searching algorithms · 搜索算法
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | è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)和二分查找(binary search)、各自的性能,以及怎样选择。
Linear search
- 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
线性查找
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // 未找到
- 它从头走起,把每个元素与目标比较,找到匹配或走到末尾就停下。
- 它对任何列表都有效,有序无序都行,对任何能逐个走过的结构也都有效。
- 最坏情况:目标在最后或根本不在,于是全部 $n$ 个元素都被比较,即 $O(n)$。平均大约一半。
一次一个,从头开始
A linear search: · 一个线性搜索:
Linear search needs no preparation and works on any list, at worst O(n). · 线性搜索不需要准备并在任何列表上工作,最坏 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
- 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.
二分查找
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
- 它要求数据有序。把中间元素与目标比较:相等就停;目标更大就丢掉下半部分;否则丢掉上半部分。
- 每次比较把还要搜索的范围减半,所以比较次数是 $O(\log_2 n)$。
- 这就是一百万项只需约二十次比较的原因:$2^{20}$ 刚过一百万。
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. · $\log_2(1\,000\,000) \approx 20$——大约 20 次比较。
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. · 二分查找是 O(log n),因为每次比较把还要搜索的范围____。
Twenty halvings take a million down to one, which is why 2^20 being just over a million is the number to remember. · 减半二十次就把一百万降到一,这就是要记住 2^20 刚过一百万的原因。
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.
例题:追踪一次二分查找
- 有序列表是 2, 5, 8, 12, 16, 23, 38, 56, 72, 91。追踪对 23 的查找。
low是 1,high是 10,所以mid是 5,那里是 16。16 小于 23,所以丢掉下半部分:low变成 6。low6、high10,所以mid是 8,那里是 56。56 大于 23,所以high变成 7。low6、high7,所以mid是 6,那里是 23。找到,用了三次比较,而线性查找要六次。- 每一步都要写出
low、high、mid和那里的值。大部分分数在追踪过程里,不在答案里。
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? · 在有序列表 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 中,二分查找找到 23 需要几次比较?
mid 5 holds 16 (too small), mid 8 holds 56 (too large), mid 6 holds 23. A linear search would have taken six. · mid 5 是 16(太小),mid 8 是 56(太大),mid 6 是 23。线性查找要六次。
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.
在两者之间选择
| 线性 | 二分 | |
|---|---|---|
| 数据必须有序 | 否 | 是 |
| 最坏情况比较次数 | $n$ | $\log_2 n$ |
| 一百万项 | 最多 1,000,000 | 约 20 |
| 适合 | 无序或小列表、链表 | 反复查找的大型有序数组 |
- 先排序的代价大于一次线性查找,所以只有当列表已经有序、或者会被查找很多次时,二分查找才划算。
- 二分查找还需要对中间元素的直接存取,数组有,链表没有。
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.
例题:论证选择
- 一个程序在 50 条无序记录中查找一次。 线性查找:先给列表排序的代价远大于这次查找所需的 50 次比较。
- 一个程序每秒在一百万条有序记录中查找上千次。 二分查找:数据已经有序,每次查找约 20 次比较而不是最多一百万次。
- 一个程序在链表中查找。 线性查找:二分查找需要直接跳到中间元素,而链表只能从头往下走。
- 说出算法,再说出决定它的那条数据性质。
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). · 二分搜索快得多(O(log n))但只在已排序的数据上;线性在任何地方以 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.
保持文件有序的代价
- 二分查找只能用在已排序的列表上,而排序不是免费的。要求你论证选择的题,问的就是这笔账。
- 如果数据经常被查、很少被改,就排序一次,以后每次查找都是 $\log_2 n$。字典或查找表就是这种情形。
- 如果数据不断变化,每次插入都要维持顺序,代价是把后面的元素移位。那么在无序数据上做线性查找,总代价反而可能更低。
- 数字能把论证说实:一百万条记录线性查找最多要比较一百万次,而二分查找只要 20 次,因为 $2^{20} > 10^6$。
- 所以评分认可的答案要说出两半:被查得多频繁,以及被改得多频繁。
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.
容易丢掉的分
- 二分查找要求数据有序。不带这个条件只说"它更快"会丢分。
- 每一步把范围减半,这就是 $\log_2 n$ 的来源。要给出理由,不只是记号。
- 两种查找都必须能报告未找到,那个
-1和循环条件就是干这个的。 - 二分查找需要直接存取,所以即使链表有序,它也用不上。
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
你掌握了
- 线性查找从头逐个比较,对任何列表都有效,是 $O(n)$
- 二分查找需要有序且能直接存取的数据,比较中间元素并每次把范围减半,得到 $O(\log_2 n)$:一百万项约 20 次比较
- 追踪二分查找时要在每一步写出
low、high、mid和那里的值 - 从数据出发选择:无序、很小或是链表就用线性;大、有序且常被查找就用二分