Algorithms: searching
Python for AP CS Principles Lesson 9 2:08 English narration · English + 中文 subtitles burned in
Chapters
Transcript
An algorithm is a clear, finite list of steps that solves a problem, and searching is the classic one: find where a value sits in a list.
算法是一串清晰的、有限的步骤，用来解决一个问题， 而查找是其中最经典的一个：找出某个值在列表里的位置。
Linear search checks the items one by one, from the start.
线性查找从头开始，一个一个地检查。
Watch the counter — one look, two, three, and it keeps going until it lands on thirteen at the seventh.
看那个计数器——看了一次、两次、三次， 一直走到第七次才落在 13 上。
It works on any list at all.
它对"任何"列表都管用。
And if you reach the end without finding it, you return minus one.
而如果你走到末尾还没找到，就返回 -1。
Now the same list and the same target, but the list is sorted — and that changes everything.
现在还是同一个列表、同一个目标，但列表是"排过序"的—— 而这一点改变了一切。
Look at the middle item.
看中间那一项。
Thirteen is bigger than seven, so the whole left half is gone, in one step.
13 比 7 大，所以整个左半边一步就没了。
Look at the middle of what is left.
再看剩下部分的中间。
Bigger again, so half of that goes too.
又比它大，于是那一半也没了。
Look once more, and there it is.
再看一次，它就在那里。
Three looks instead of seven, because each look throws away half the list.
三次，而不是七次， 因为每看一次，就扔掉一半的列表。
Both searches are built out of the same three blocks you already know.
这两种查找，都是由你已经学过的同样三块积木搭起来的。
Sequencing: the steps happen in order.
顺序：步骤按次序发生。
Selection: an if decides what happens next.
选择：由 if 决定接下来做什么。
Iteration: a loop repeats the check.
迭代：由循环把检查一遍遍重复。
You have just watched a search use all three — and naming those three is the answer the exam is looking for.
你刚刚亲眼看着一个查找把这三样都用上了—— 而说得出这三个名字，正是考试要的答案。
Here is a search written the exam's way.
这是按考卷写法写出来的一个查找。
FOR EACH visits every item, IF makes the decision, and RETURN sends the answer back.
FOR EACH 走遍每一项，IF 做判断，RETURN 把答案送回去。
Same three blocks, different notation — and remember the single equals in the exam's IF, because that compares, it does not store.
还是那三块积木，只是记法不同—— 另外记住考卷 IF 里那个"单个等号"， 它是比较，不是赋值。
Four things to take with you.
带走四点。
One: linear search checks each item in turn, on any list.
第一：线性查找逐项检查，任何列表都能用。
Two: binary search throws away half the list each look.
第二：二分查找每看一次就扔掉一半列表。
Three: binary search only works on a sorted list.
第三：二分查找只对"排过序"的列表有效。
Four: algorithms are built from sequencing, selection and iteration.
第四：算法是由顺序、选择和迭代搭起来的。
Now write the searches in the tasks below.
现在去下面的题里把这两种查找写出来。