Searching
Java for AP CS A Lesson 13 1:41 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Linear search checks the items one after another from the start.
线性查找从头开始，一个接一个地检查。
Watch the counter climb: one look, two, three, and it keeps going until it lands on thirty-eight at the seventh.
看那个计数器往上爬：看一次、两次、三次， 一直走到第七次才落在 38 上。
It works on any array at all, sorted or not.
它对任何数组都管用，排没排过序都行。
And if the loop finishes without a match, you return minus one.
而如果循环走完了还没匹配上，就返回 -1。
Binary search needs the array sorted, and in exchange it is dramatically faster.
二分查找要求数组是排好序的，作为交换，它快得惊人。
Start in the middle.
从中间开始。
Thirty-eight is bigger than twelve, so the whole left half is gone in one step.
38 比 12 大，于是整个左半边一步就没了。
Middle of what is left: still bigger, so half of that goes too.
再看剩下部分的中间：还是更大，那一半也没了。
One more look and there it is.
再看一次，它就在那儿。
Three looks, not seven — and on a thousand items it would be about ten instead of a thousand.
三次，而不是七次—— 而在一千个元素上，会是大约十次，而不是一千次。
In code it is a while loop with two markers, low and high.
写成代码，就是一个带两个标记 low 和 high 的 while 循环。
Each pass takes the middle.
每一轮取中点。
If the middle is too small, move low past mid.
如果中间那个太小，就把 low 移到 mid 后面。
If it is too big, move high below mid.
如果太大，就把 high 移到 mid 前面。
And when low passes high, the range has closed with nothing in it — the value is not there, so return minus one.
而当 low 越过 high 时，区间已经收成空的了—— 那个值不在里面，所以返回 -1。
Four things to take with you.
带走四点。
One: linear search checks each item, on any array.
第一：线性查找逐项检查，任何数组都行。
Two: binary search only works on a sorted array.
第二：二分查找只对排好序的数组有效。
Three: each look throws away half of what is left.
第三：每看一次就扔掉剩下的一半。
Four: when low passes high, the value is not there.
第四：当 low 越过 high 时，那个值不存在。
Now write both searches in the tasks below.
现在去下面的题里把两种查找都写出来。