此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
我们要做什么
- 算法(algorithm)是一份解决问题的清晰步骤清单。
- 一个很常见的任务是搜索:找出某个值在列表中的位置。
- 我们要学两个算法:线性搜索和二分搜索。
线性查找
- 一个一个地检查元素,从头到尾。
- 如果找到了这个值,就返回它的索引(位置)。
- 如果一直到末尾都没找到,就返回
-1。
English
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
为什么有序列表有帮助
- 线性搜索对任何列表都有效,哪怕是乱序的。
- 但如果列表是有序的(从小到大),我们可以快得多。
- 二分搜索利用有序的顺序,每次跳过一半的列表。
二分查找
- 看中间的元素。
- 如果它就是目标,你就完成了。
- 如果目标更小,就搜索左半边;如果更大,就搜索右半边。重复这个过程。
English
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
把这些想法组合起来
- 一次搜索组合了三个你已经学过的基本部件。
- 顺序:按次序执行步骤。选择:
if/elif/else。 - 迭代:用循环(
for或while)重复检查。
在 AP CSP 伪代码中
- 考试会像这样写一个循环和一个检查。
FOR EACH访问每个元素;IF做选择;REPEAT UNTIL一直循环到某个条件为真。
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
常见错误
- 二分查找需要一个已排序的列表。
- 线性查找逐个检查每个元素。
现在轮到你
- 每个任务给出一个过程名字以及它必须返回什么。
- 按检查答案来测试你的代码。
探索
在列表中查找
二分查找需要有序列表,但比线性快得多。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
写 linear_search(lst, target)。返回 target 在 lst 中的索引,如果不在就返回 -1。一个一个地检查元素。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
为一个从小到大排好序的列表写 binary_search(sorted_lst, target)。返回 target 的索引,或 -1。看中间元素,每次把搜索范围减半。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
写 contains(lst, target),如果 target 在 lst 里就返回 True,否则返回 False。你可以复用线性搜索,把结果和 -1 比较。
点击“运行”查看此处输出。