Searching
Python for A-Level CS Lesson 7 2:14 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Searching means finding whether a value is in a list, and where.
查找的意思是：判断某个值在不在列表里，以及它在哪里。
Note the second half of that: what comes back is the position, not the value — the caller already knows what they asked for.
注意后半句：返回的是位置，不是值—— 调用者本来就知道自己找的是什么。
Linear search checks each item in turn and returns the index the moment it matches.
线性查找逐个检查，一旦匹配就立刻返回下标。
If the loop runs out, it returns minus one, which is safe because minus one is never a real index.
如果循环跑完了，就返回 -1， 这是安全的，因为 -1 永远不会是一个真实的下标。
If the list is sorted you can do far better.
如果列表是有序的，你可以做得好得多。
Jump to the middle and compare.
直接跳到中间去比较。
Looking for thirteen, the middle is seven — too small, and because the list is in order, everything to its left is gone in one comparison.
要找 13，中间是 7——太小了， 而因为列表是有序的，它左边的全部只用一次比较就出局了。
Now the middle of what remains is eleven, still too small, and half of that goes too.
现在剩下部分的中间是 11，还是太小，那一半也去掉。
Keep halving and you are left with one item standing.
这样一直折半，最后只剩下一个元素站着。
Put figures on it and the difference stops being abstract.
给它配上数字，这个差别就不再抽象了。
Ten items: ten checks or four.
10 个元素：10 次检查，或者 4 次。
A thousand: a thousand, or ten.
1000 个：1000 次，或者 10 次。
A million: a million, or twenty.
100 万个：100 万次，或者 20 次。
Look at the right-hand column — every doubling of the list adds one step to binary search, and one only.
看右边那一列——列表每翻一倍，二分查找只多一步，就一步。
That relationship is what an exam question about efficiency is asking you to describe.
这个关系，正是考试问"效率"时要你描述的东西。
In code, the surviving window is two variables, low and high, with mid between them.
在代码里，还活着的那个区间就是两个变量：low 和 high，中间点在它们之间。
If the middle is too small, low moves past it; too big, and high moves back; and when low passes high the window is empty, so the answer is minus one.
如果中间的值太小，low 移到它后面；太大，high 往回移； 而当 low 越过 high 时，区间就空了，答案是 -1。
One notation note for the paper: DIV means whole-number division, which is Python's double slash.
关于考卷写法的一点说明： DIV 表示整数除法，也就是 Python 里的双斜杠。
Four things to take with you.
带走四点。
One: linear search works on any list and returns an index.
第一：线性查找对任何列表都成立，返回的是下标。
Two: binary search halves the range every step.
第二：二分查找每一步把范围减半。
Three: but it is only correct on a sorted list.
第三：但它只有在已排序的列表上才是正确的。
Four: for a million items that is a million checks, or twenty.
第四：一百万个元素，就是一百万次检查，或者二十次。
Now write all three functions.
现在把那三个函数都写出来。