一、一个一个看：线性搜索

在 0 到 999 这一千个数里找 785。线性搜索的做法：从 0 开始，一个一个看。 演示里第 786 个才碰上，比了 786 次——因为 0 到 784 一共 785 个数，785 排在第 786 位。 再找 1000（不存在）：要比满 1000 次才敢说没有。

这就是线性搜索的代价：它跟你找的东西在第几个直接挂钩。在第 1 个就 1 次，在最后就 1000 次。 平均下来是一半，最坏是全看一遍。所以它的复杂度写成 O(n)——n 是数据的个数，不是「几次」。

二、每次砍一半：二分搜索

同样找 785，二分搜索的做法完全不同：先看中间那个。 演示里的九步：499、749、874、811、780、795、787、783、785。每一步的范围都缩一半。 为什么是 499 起步？因为 0 到 999 的中间是 499。 785 比它大，所以左半边整片扔掉——一次就扔了五百个数。

九次就把一千个数筛到只剩一个。这不是运气，是对半砍的必然结果。 对半砍的代价是 O(log n)：1000 只要 10 次，100 万只要 20 次。数据翻一千倍，只多比 10 次。

三、数据翻一千倍，二分只多比 10 次

演示里那张表是这一节最该记住的：

为什么 1000 是 10 次？因为 2 的 10 次方是 1024，比 1000 大。 每次砍一半，砍 10 次就把一千个数砍完。 100 万是 2 的 20 次方附近，10 亿是 2 的 30 次方附近。这就是第 5.5 那三个 2 的次方的用处。 所以二分搜索的快不是「常数小」，是复杂度换了量级：从 O(n) 换到 O(log n)。

四、二分的前提：数据必须排好

演示里那个反例最值得看：乱序的 3 1 4 1 5 9 2 6，用二分找 4，没找到。 但 4 确实在里面，就在下标 2。 二分没找到，不是因为代码写错，是前提不成立。 二分每一步都在「扔掉一半」，而扔掉的前提是「那一半里的数不可能更大/更小」。 乱序的时候这个前提是假的。

最要命的是：它不报错，只是悄悄给你一个「没有」。这类错误在生产环境里能查一整天。 所以有一条铁律：用二分之前，先确认数据真的有序。不是「大概有序」，是每一对相邻元素都满足条件。

五、先排序再二分，才是一套

那二分这么危险，还值得用吗？值得，但要连排序一起算账。 排序一次是 O(n log n)，之后每次查找 O(log n)。 只查一次，不如直接线性扫一遍；查很多次，排序的钱就赚回来了。 举个量级：100 万个数据，线性查一次最多 100 万次；排序约 2000 万步，之后每次查找 20 次。 查过一千次就明显划算。

这条账在真实系统里天天要算。 数据库建索引本质上就是「先排好，以后每次查都快」——只是它把这个顺序持久化了，不用每次重排。 这也解释了为什么索引不能乱建：它赌的是「查得多」。一张只写不查的表，索引纯粹是负担。 下一节 6.4 会看到实测数据。

六、动手 Demo：一千个数里找一个数：一个一个看，还是对半砍

先在 0 到 999 里线性找 785，数一数比了几次；再找一个不存在的数，看最坏情况。 再用二分找同一个数，把每一步的中间值打出来。 最后拿一组乱序数据做反例：二分会告诉你「没找到」。

data = list(range(1000))

cnt = 0
for i, v in enumerate(data):
    cnt += 1
    if v == 785:
        print('线性找到', v, '在下标', i, '比了', cnt, '次')
        break

target, lo, hi, step, cnt2 = 785, 0, len(data) - 1, [], 0
while lo <= hi:
    mid = (lo + hi) // 2
    step.append(data[mid])
    cnt2 += 1
    if data[mid] == target:
        break
    if data[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print('二分走的中间值', step)
print('二分比了', cnt2, '次')

bad = [3, 1, 4, 1, 5, 9, 2, 6]
found = False
lo, hi = 0, len(bad) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if bad[mid] == 4:
        found = True
        break
    if bad[mid] < 4:
        lo = mid + 1
    else:
        hi = mid - 1
print('乱序里二分找 4：', found, '但 4 在下标', bad.index(4))

实跑输出：

--------------------------------------------------------------------
线性搜索与二分搜索
--------------------------------------------------------------------


  ① 一个一个看：线性搜索
  --------------------------------------------------------------------
  在 0 到 999 里找 785
  从头开始看，第 786 个才碰上，比了 786 次
  找一个不存在的数：比满 1000 次才敢说没有
  线性搜索的代价是「目标在第几个」。在第 1 个就 1 次，在最后就 1000 次，找不到要 1000 次。
  平均下来一半，最坏全看一遍。

  ② 每次砍一半：二分搜索
  --------------------------------------------------------------------
  每次看中间那个：499 -> 749 -> 874 -> 811 -> 780 -> 795 -> 787 -> 783 -> 785
  比了 9 次就找到

| 数据量 | 线性最多几次 | 二分最多几次 |
|---:|---:|---:|
| 1000 | 1000 | 10 |
| 100 万 | 100 万 | 20 |
| 10 亿 | 10 亿 | 30 |

  数据翻一千倍，二分只多比 10 次。这就是「砍一半」的威力：1000 是 2 的 10 次方，所以 10 次到底。

  ③ 二分有个前提：数据必须已经排好
  --------------------------------------------------------------------
  没排序的一组数：[3, 1, 4, 1, 5, 9, 2, 6]
  用二分找 4：没找到
  但它确实在里面，下标 2
  二分没找到，不是因为代码错，是因为前提不成立。
  乱序数据用二分，结果不可信——而且它不报错，只是悄悄给你一个「没有」。
  所以「先排序再二分」才是一套。
  单独看二分很快，但它把排序的成本转移到了前面：只查一次不划算，查很多次就很划算。
  数据库建索引就是这个道理。

①线性那段从 0 开始数，785 在第 786 位，所以比了 786 次。 下标和「第几个」差 1，这个细节在这类题里反复出现。 ②二分的循环条件是 lo <= hi，每一步改的是 lo 或 hi。 mid 每轮重算——范围缩小了，中间点自然跟着变。 ③九个中间值和演示里完全一致。这不是碰巧，二分只有这一条路。 ④反例那段输出 False，但下一句就告诉你 4 在下标 2。这就是最危险的一类错误：结果错、不报错。

30 秒实验

1. 把目标改成 0 和 999，看线性搜索各比几次（这就是最好和最坏）。
2. 用 100 万个数重跑二分，数一数比了几次，验证「20 次左右」。
3. 把乱序那段改成先 sort() 再二分，看能不能找到 4。

常见误区

1. 「二分搜索很快，所以能用的地方就用。」前提是有序，乱序用了会悄悄返回「没有」。
2. 「乱序用二分，最多少找到几个。」不是少找到，是结果完全不可信，而且不报错。
3. 「二分比线性好，不用考虑排序成本。」只查一次时，排序比线性扫一遍贵得多。

二分虽然快，但它要求「排好序」这个前提。有没有既不用排序、又只要一次的办法？下一节讲哈希表。

• ☐ （本篇完，下一篇 6.2 哈希表：一次就找到）

相关笔记

• 哈希表：一次就找到
• 树与二叉树
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引