词汇
| English | 释义 | 拼音 |
|---|---|---|
| Searching/ˈsɜːtʃɪŋ/ | 查找 | chá zhǎo |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
| sorted/ˈsɔːtɪd/ | 已排序 | yǐ pái xù |
查找一个值
- 查找指在一个集合中定位目标值。
- 两个标准算法:线性查找和二分查找。
- 两者都返回目标所在的下标——或一个“未找到”信号(常为
-1)。 - 你能用哪一个,取决于数据是否已排序。
线性查找
- 从头开始逐个检查每个元素,直到找到目标。
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- 对任何数组都有效——排序与否都行。
- 最坏情况:它检查每个元素(
n次检查)。

线性搜索依次检查每个元素直到找到目标

二分搜索每一步都将范围减半
二分查找
- 需要一个已排序的数组。每次看中间的元素。
- 若中间就是目标,完成。若目标更小,查找左半;若更大,查找右半。
- 每一步把剩下要查的范围减半。
- 在大的已排序数组上快得多——约
log₂ n次检查,而非n。
二分查找为何快
- 对一百万个元素做线性查找:多达一百万次检查。
- 对一百万个已排序元素做二分查找:约 20 次检查。
- 代价:数组必须已经排好序。
- 反复减半是
O(log n)背后的大主意。
注意
二分查找只对已排序数组有效——在未排序数据上运行会给出错误答案。它还是与中间比较、每步丢弃一半范围;线性查找从开头比较、每次只丢一个元素。若你不确定数据是否已排序,就必须用线性查找(或先排序)。
例子
在 [1, 3, 5, 7, 9] 中二分查找 7:
- 中间是
5(下标 2)。7 > 5,所以查找右半。 - 右半是
[7, 9];中间是7。在下标 3 找到。 - 两次检查而非四次——范围每次减半。
关键点
线性查找从头检查元素(对任何数组有效,最多 n 次检查)。二分查找需要一个已排序数组,与中间比较,每步把查找范围减半(约 log₂ n 次检查)。两者都返回找到的下标,或一个像 -1 的“未找到”信号。
探索
线性 vs 二分查找
二分查找每步把已排序范围减半。
练习
线性查找……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
线性 = 从头到尾;对任何数组都行。
练习
二分查找要求数组是……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
二分查找只对已排序数据有效。
练习
二分查找的每一步……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
它与中间比较并保留一半。
练习
在 [1,3,5,7,9] 中二分查找 7:多少次比较(每次取中间)?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
先比 5,再比 7——两次比较。
练习
二分查找在未排序数组上给出正确结果。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
它依赖顺序;未排序数据会破坏它。
练习
把每种查找与其性质配对。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
线性通用但较慢;二分快但需要顺序。