Searching · 查找
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
English
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
中文
在列表中查找
- 查找(searching)就是判断某个值是否在列表中,以及在哪里。
- 通常的答案是这个值的索引,如果不存在则返回
-1。 - 两种经典方法是线性查找和二分查找。
English
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
中文
线性查找
- 从头开始,依次检查每个元素。
- 一旦找到匹配项就停下。
- 它对任何列表都有效,无论是否已排序。
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
English
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
中文
二分查找
- 二分查找需要一个已排序的列表。
- 看中间那个元素。如果它就是目标,就停下。
- 如果目标更小,就在左半边找;更大就在右半边找。
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
English
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
中文
比较两者
- 线性查找可能要检查每一个元素 —— 对长列表来说很慢。
- 二分查找每一步都丢掉一半列表,所以快得多。
- 但二分查找只有在数据已经排好序时才有效。
English
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
中文
用剑桥伪代码表示
- 注意
DIV是整数除法(对应 Python 的//)。
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
English
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
中文
常见错误
- 二分查找需要已排序的列表;每一步把范围减半。
- 线性查找对任何列表都有效,但更慢。
English
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
中文
现在轮到你
- 返回该值的索引,找不到时返回
-1。 - 按检查答案来测试你的代码。
Explore · 探索
Linear vs binary search · 线性查找 vs 二分查找
Binary search · 二分查找 halves the list each step — far fewer comparisons. · 二分查找每一步都把范围减半——比较次数少得多。
Write linear_search(items, target) that returns · 返回值 the index of target in · 入 items, or -1 if it is not there. Check the items one by one. · 编写 linear_search(items, target),返回 target 在 items 中的索引,如果不存在则返回 -1。逐个检查元素。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · 为已排序的列表编写 binary_search(items, target)。返回 target 的索引,找不到则返回 -1。每一步把范围减半。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write first_negative(items) that scans the list and returns · 返回值 the index of the first number less than 0, or -1 if there are none. · 编写 first_negative(items),扫描列表并返回第一个小于 0 的数字的索引,如果没有则返回 -1。
Click Run to see the output here. · 点击“运行”查看此处输出。