此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
在列表中查找
- 查找(searching)就是判断某个值是否在列表中,以及在哪里。
- 通常的答案是这个值的索引,如果不存在则返回
-1。 - 两种经典方法是线性查找和二分查找。
线性查找
- 从头开始,依次检查每个元素。
- 一旦找到匹配项就停下。
- 它对任何列表都有效,无论是否已排序。
English
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
二分查找
- 二分查找需要一个已排序的列表。
- 看中间那个元素。如果它就是目标,就停下。
- 如果目标更小,就在左半边找;更大就在右半边找。
English
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)
比较两者
- 线性查找可能要检查每一个元素 —— 对长列表来说很慢。
- 二分查找每一步都丢掉一半列表,所以快得多。
- 但二分查找只有在数据已经排好序时才有效。
用剑桥伪代码表示
- 注意
DIV是整数除法(对应 Python 的//)。 - 剑桥数组通常从 1 运行到
n,即项目数量。LENGTH()用于字符串,因此循环使用n。
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
常见错误
- 二分查找需要已排序的列表;每一步把范围减半。
- 线性查找对任何列表都有效,但更慢。
现在轮到你
- 返回该值的索引,找不到时返回
-1。 - 按检查答案来测试你的代码。
探索
线性查找 vs 二分查找
二分查找每一步都把范围减半——比较次数少得多。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
编写 linear_search(items, target),返回 target 在 items 中的索引,如果不存在则返回 -1。逐个检查元素。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
为已排序的列表编写 binary_search(items, target)。返回 target 的索引,找不到则返回 -1。每一步把范围减半。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
编写 first_negative(items),扫描列表并返回第一个小于 0 的数字的索引,如果没有则返回 -1。
点击“运行”查看此处输出。