Algorithms: searching · 算法:搜索
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
我们要做什么
- 算法(algorithm)是一份解决问题的清晰步骤清单。
- 一个很常见的任务是搜索:找出某个值在列表中的位置。
- 我们要学两个算法:线性搜索和二分搜索。
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
线性搜索
- 一个一个地检查元素,从头到尾。
- 如果找到了这个值,就返回它的索引(位置)。
- 如果一直到末尾都没找到,就返回
-1。
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))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
为什么有序列表有帮助
- 线性搜索对任何列表都有效,哪怕是乱序的。
- 但如果列表是有序的(从小到大),我们可以快得多。
- 二分搜索利用有序的顺序,每次跳过一半的列表。
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
二分搜索
- 看中间的元素。
- 如果它就是目标,你就完成了。
- 如果目标更小,就搜索左半边;如果更大,就搜索右半边。重复这个过程。
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))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
把这些想法组合起来
- 一次搜索组合了三个你已经学过的基本部件。
- 顺序:按次序执行步骤。选择:
if/elif/else。 - 迭代:用循环(
for或while)重复检查。
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
用 AP CSP 伪代码表示
- 考试会像这样写一个循环和一个检查。
FOR EACH访问每个元素;IF做选择;REPEAT UNTIL一直循环到某个条件为真。
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
常见错误
- 二分查找需要已排序的列表。
- 线性查找逐个检查每个元素。
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
现在轮到你
- 每个任务给出一个过程名字以及它必须返回什么。
- 按检查答案来测试你的代码。
Searching a list · 在列表中查找
Binary search needs a sorted list but is far faster than linear. · 二分查找需要有序列表,但比线性快得多。
Write linear_search(lst, target). Return the index of target in · 入 lst, or -1 if it is not there. Check items one by one. · 写 linear_search(lst, target)。返回 target 在 lst 中的索引,如果不在就返回 -1。一个一个地检查元素。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · 为一个从小到大排好序的列表写 binary_search(sorted_lst, target)。返回 target 的索引,或 -1。看中间元素,每次把搜索范围减半。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · 写 contains(lst, target),如果 target 在 lst 里就返回 True,否则返回 False。你可以复用线性搜索,把结果和 -1 比较。
Click Run to see the output here. · 点击“运行”查看此处输出。