| English | 释义 | 拼音 |
|---|---|---|
| sorted/ˈsɔːtɪd/ | 已排序 | yǐ pái xù |
| Binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
| target/ˈtɑːɡɪt/ | 目标 | mù biāo |
| middle/ˈmɪdl/ | 中间 | zhōng jiān |
| halves/hɑːvz/ | 减半 | jiǎn bàn |
| comparison/kəmˈpærɪsn/ | 比较 | bǐ jiào |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
在已排序列表中快速查找
- 二分查找(binary search)是在已排序(sorted)列表中定位一个目标(target)值的快速方法。
- "已排序"意味着值是有序的——比如从小到大。
- 它比检查每一项快得多。
- 但它有一个严格的要求。
二分查找需要已排序的数据。 在未排序的列表上,它可能跳过目标而错过它。总是先排序——或用另一种查找。
二分查找只能用在什么样的数据上:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
在未排序数据上它可能错过目标。
检查中间,然后减半
- 想法很简单:检查中间(middle)元素。然后:
- 如果中间等于目标,你找到了;
- 如果目标更小,只搜索左半;
- 如果目标更大,只搜索右半。

二分搜索每步将范围减半(列表必须已排序)
线性 vs 二分查找
二分每步把范围减半
线性查找检查每个项;二分查找每次比较把已排序列表减半,所以需要少得多的步骤。
如果目标大于中间元素,二分查找接下来看:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
更大的目标必在右(更高的)半。
二分查找中每次比较把列表剩余部分______。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每步减半是它这么快的原因。
一个 1000 项的已排序列表大约需要多少次二分查找?(2^10 = 1024)
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
因为 2^10 = 1024 ≥ 1000,约 10 次减半就够。
为什么它这么快
- 每次比较(comparison)都会使列表的剩余部分减半。
- 对 1000 项,线性搜索可能需要多达 1000 次检查。
- 二分查找最多需要约 10 次,因为 $2^{10} = 1024$。
- 列表越大,优势越大。
二分法在[2,5,8,11,14,17,20]中查找14需要多少次比较?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
中间 11 → 右;中间 17 → 左;中间 14 → 找到:3 次比较。
在大型已排序列表中,线性搜索所需的比较次数少于二分搜索。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
错误。二分搜索每一步将列表减半,因此所需的比较次数远少于逐一检查每个元素。
对比线性搜索
- 一个线性查找(linear search)一个一个地检查每个元素。
- 二分查找在大的已排序列表上通过每步减半胜过它。
在 [2, 5, 8, 11, 14, 17, 20] 中搜索 14。 中间是 11;14 > 11 → 搜索右半 [14, 17, 20]。中间是 17;14 < 17 → 搜索 [14]。中间是 14——只用 3 次比较找到。线性搜索本会用 5 次。
二分查找通过检查中间并只保留可能含有它的那一半,在已排序列表中找到目标。每次比较****减半范围,所以 1000 项需要约 10 次检查——远少于线性查找的 1000 次。它只在已排序数据上有效。