Searching
C Programming Lesson 12 2:30 English narration · English + 中文 subtitles burned in
Chapters
Transcript
You met this one last lesson.
这个你上一课见过了。
Linear search checks the items one after another, from the front, and returns the index as soon as one matches.
线性查找从前往后一个接一个地检查，一旦匹配就返回下标。
If the loop runs out, it returns minus one.
如果循环跑完了，就返回 -1。
Its strength is that it asks nothing of the data: it works on any array at all, in any order.
它的长处是对数据毫无要求：任何数组、任何顺序它都能用。
Its weakness is the count.
它的短处在于次数。
For a thousand items it may look at a thousand of them.
一千个元素，它可能要看上一千次。
If the array is sorted, you can do far better.
如果数组是有序的，你可以做得好得多。
Do not start at the front — jump to the middle and compare.
不要从头开始——直接跳到中间去比较。
Suppose we are looking for thirteen and the middle is seven.
假设我们在找 13，而中间是 7。
Thirteen is bigger, and the array is in order, so it cannot possibly be to the left.
13 更大，而数组是有序的，所以它绝不可能在左边。
Everything left of the middle is gone in one comparison.
一次比较，中间左边的全部出局。
Now do the same to what remains: look at the middle again, throw away half of what is left, and again, until one item is standing.
现在对剩下的部分做同样的事：再看中间， 把剩下的一半再丢掉，再来一次，直到只剩一个。
In code, the surviving window is two variables: low and high.
在代码里，还活着的那个区间就是两个变量：low 和 high。
The middle sits between them.
中间点位于它们之间。
If the middle item is too small, the target must be to the right, so low moves past the middle.
如果中间的元素太小，目标一定在右边，于是 low 移到中间点之后。
If it is too big, the target is to the left, so high moves back.
如果太大，目标在左边，于是 high 往回移。
And when low crosses over high, the window is empty — nothing is left to check, so the answer is minus one.
而当 low 越过 high 时，区间就空了—— 没有东西可查了，所以答案是 -1。
The lesson's second task says sorted, and it means it.
课程里的第二道题写着“已排序”，而且是认真的。
Halving is not a shortcut you can take anywhere; it is a deduction, and the deduction only holds because the array is in order.
二分不是一个随处可用的捷径，它是一个推理， 而这个推理成立，只因为数组是有序的。
Run it on an array that is not in order and it will still finish, still look confident, and quietly report that a value it walked straight past is missing.
拿它跑一个没排过序的数组，它照样会跑完，照样一副很有把握的样子， 然后悄悄地告诉你：一个它刚刚路过的值不存在。
One habit does carry across: both answer minus one for a value that is not there.
有一个习惯确实是共通的： 值不存在时，两种查找都返回 -1。
Four things to take with you.
带走四点。
One: linear search works on any array, and may check all n items.
第一：线性查找对任何数组都成立，最多要查 n 个元素。
Two: binary search halves the range at every step, so a thousand items take about ten comparisons.
第二：二分查找每一步把范围减半， 所以一千个元素大约十次比较就够了。
Three: it is only correct on a sorted array.
第三：它只有在已排序的数组上才是正确的。
Four: both return minus one when the value is not there.
第四：值不存在时两者都返回 -1。
Now write both, then the third task, which is a linear search with a test instead of a target.
现在把两个都写出来，再做第三题—— 那是一次线性查找，只是把“找目标值”换成了“做一个判断”。