小探险家学算法

Appearance

11. 猜数大师（二分查找） ​

知识点：二分查找 —— 每次排除一半（O(log n)）

项目：在排好序的名单里快速找人

故事开场：作业本排好队了 ​

上一章，老师把全班作业本排好了序，然后再让你找。

你正准备"从第一本翻起"，老师拦住了你："先别急着翻。我考考你——"

"每个汉字在电脑里都有一个编号（就像字典的页码），我们按编号把作业本 排好了。这摞作业本中间那一本，是小明（编号 26126）；你要找的小华， 编号是 21326——比小明小。那么，小华一定在中间那一本的哪一边？"

你想了想："编号更小……在左边！"

"没错！"老师说，"你翻这一下，就排除了右半边。剩下左边还有一半， 你再翻它们中间的那本，又排除一半……"

你眼睛亮了："这样找，每次都排除一半！100 本作业本，翻 7 次就能找到！"

等等，这听起来好耳熟啊——第 1 章的猜数字游戏！

笨办法先行：乱序名单，二分会失灵？ ​

你立刻写了个程序，准备试试这个"每次排除一半"的办法。但你想偷懒： "名单一定要排好序吗？我先拿乱序的试试！"

ts
const shuffled = ["小明", "小红", "小刚", "小雨", "小丽"]   // 乱序！

function binarySearch(list: string[], target: string): number {
  let low = 0
  let high = list.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)   // 看正中间那个
    if (list[mid] === target) {
      return mid                               // 找到了！
    } else if (list[mid] < target) {
      low = mid + 1                            // 目标在右边
    } else {
      high = mid - 1                           // 目标在左边
    }
  }

  return -1                                    // 找不到
}

console.log(binarySearch(shuffled, "小丽"))     // 输出多少？

运行看看——结果是 -1，明明"小丽"就在名单里，却说"找不到"！

为什么？因为二分查找有个铁规矩：数据必须排好序。

"小丽"在中间（"小刚"）的右边，程序就自信地扔掉左半边去找； 可乱序名单里，左边其实藏着目标。一次错误的"排除"，就把目标扔掉了。

这就像猜数字游戏：1~1000 里猜一个数，你问"比 500 大吗"—— 前提是数确实是按大小排的。如果这个数可以随便乱跳， 你问一百次也猜不中。

引出知识点：二分查找——每次排除一半 ​

二分查找（binary search）的"二分"，就是"每次砍成两半"。

它只做一件事：看正中间那个数，判断目标在左半边还是右半边， 然后把另一半扔掉。 剩下的继续砍、继续扔，直到找到（或确定没有）。

为什么它快得离谱？看这个表：

数据量线性查找（最坏）二分查找（最多）
100100 次7 次
1 万1 万次14 次
100 万100 万次20 次
10 亿10 亿次30 次

每排除一次，数据少一半：100 万 → 50 万 → 25 万 → …… → 1， 一共大约 20 次。这就是第 1 章见过的 O(log n)——"能被除以 2 多少次"， 就是需要几步。数据涨 100 万倍，步数只涨 10 步！

动手实现：二分查找 ​

在排好序的名单上，写正式的二分查找。注意：名单必须按电脑的规则 排好——电脑不认识拼音，它给每个汉字都编了号（就像字典的页码）， "排好序"就是按编号从小到大：

ts
// 排好序的名单（按汉字的编号，从小到大）
const sorted = ["小丽", "小刚", "小明", "小红", "小雨"]

// 二分查找：在排好序的 list 里找 target
function binarySearch(list: string[], target: string): number {
  let low = 0               // 可能的范围：从 low 到 high
  let high = list.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)   // 正中间那个

    if (list[mid] === target) {
      return mid                               // 找到了！
    } else if (list[mid] < target) {
      low = mid + 1                            // 目标比中间大 → 在右半边
    } else {
      high = mid - 1                           // 目标比中间小 → 在左半边
    }
  }

  return -1                                    // 范围都空了，真没有
}

console.log("小明在第 " + binarySearch(sorted, "小明") + " 位")
console.log("小红在第 " + binarySearch(sorted, "小红") + " 位")
console.log("小华：" + binarySearch(sorted, "小华"))

输出：

小明在第 2 位
小红在第 3 位
小华：-1

用具体的数走一遍"找小红"（下标从 0 数）：

  • low=0, high=4，中间是第 2 位"小明"
  • "小红"比"小明"大？是 → low = 3（右半边：小红、小雨）
  • low=3, high=4，中间是第 3 位"小红" → 命中！返回 3

每一步，搜索范围都少一半。找 5 个名字只要 2~3 步，找 100 万个只要 20 步。

小知识：想自己验证名单是不是"真的排好序"，用这个办法—— 检查每一对相邻的名字，前面的编号必须比后面的小： sorted[0] < sorted[1] < sorted[2] ...。乱序名单会让二分查找失灵 （还记得开场那个 -1 吗）。

跑起来：二分 vs 线性，计时对决 ​

拿 100 万个排好序的数，分别用线性查找和二分查找找"999999"， 看看差多少：

ts
// 100 万个排好序的数
const cards: number[] = []
for (let i = 1; i <= 1000000; i++) {
  cards.push(i)
}

// 线性查找：从头找到尾
console.time("线性查找")
let found1 = -1
for (let i = 0; i < cards.length; i++) {
  if (cards[i] === 999999) { found1 = i }
}
console.timeEnd("线性查找")

// 二分查找：每次排除一半
console.time("二分查找")
const found2 = binarySearch(cards.map(String), "999999")
console.timeEnd("二分查找")

等等——binarySearch 要的是字符串数组，这里 cards 是数字数组。 我们换一个写法，直接给二分查找传数字数组：

ts
function binarySearchNumber(list: number[], target: number): number {
  let low = 0
  let high = list.length - 1
  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (list[mid] === target) {
      return mid
    } else if (list[mid] < target) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return -1
}

console.time("线性查找")
let found1 = -1
for (let i = 0; i < cards.length; i++) {
  if (cards[i] === 999999) { found1 = i }
}
console.timeEnd("线性查找")

console.time("二分查找")
const found2 = binarySearchNumber(cards, 999999)
console.timeEnd("二分查找")

在我这台电脑上，输出（数字可能不一样）：

线性查找: 3ms
二分查找: 0.1ms

3 毫秒 vs 0.1 毫秒——差了约 30 倍！而且数据越大，差距越离谱： 10 亿个数，线性要好几秒，二分还是 0.1 毫秒上下（步数只从 20 涨到 30）。

小挑战 ​

  1. 找最左和最右：如果一个数组里有重复的数，比如 [1, 2, 3, 3, 3, 4, 5]，二分查找会返回中间那一个"3"。 想一想：怎么改，才能找到最左边的那个 3？ （提示：找到 3 之后不急着返回，继续往左边找。）
  2. 数字版猜数：用二分查找在 1~1000 里找目标数，顺便数一数 它走了几步（提示：像第 1 章那样加个计数器）。
  3. 字典查词：造一个排好序的单词表，用二分查找"查字典"。 注意：查词之前，单词表必须已经排好序——试试打乱它，再查一次。

课后练习 ​

第 1 题（动手题）：找数字 ​

在 [3, 8, 12, 17, 25, 31, 42, 56, 63, 78] 里，用二分查找找 17， 手动走一遍（在纸上写出每次的 low、mid、high），再用程序验证。

参考答案（点开查看）
  • low=0, high=9，mid=4（值是 25）。17 < 25 → high=3
  • low=0, high=3，mid=1（值是 8）。17 > 8 → low=2
  • low=2, high=3，mid=2（值是 12）。17 > 12 → low=3
  • low=3, high=3，mid=3（值是 17）。命中！返回 3

只用了 4 步就找到了 10 个数里的目标。程序跑出来也应该是 3。

第 2 题（思考题）：为什么必须排好序？ ​

用自己的话解释：为什么二分查找要求数据必须排好序？ 如果数据乱序，二分查找会出什么问题？（可以拿上面的 "乱序名单"例子说。）

参考答案（点开查看）

二分查找的核心动作是"比较中间值，排除一半"。这个动作成立的前提是： 比中间值小的一定在左边，比中间值大的一定在右边——只有排好序 的数据才保证这一点。

乱序时，"目标在右边"的判断可能是错的（目标其实在左边）， 程序把正确的半边扔掉了，自然找不到。就像猜数字游戏里的数 如果乱跳，你问"比 500 大吗"就毫无意义。

铁规矩：要二分，先排序。

第 3 题（思考题）：20 步的魔法 ​

100 万个数，二分查找最多 20 步；那 100 亿（10,000,000,000）个数呢？ 最多多少步？它比 100 万的 20 步多几步？这个"多一点点"的特点叫什么？

参考答案（点开查看）

100 亿 ≈ 2 的 34 次方，最多约 34 步。

数据从 100 万涨到 100 亿（涨了 1000 倍），步数只从 20 涨到 34 （多了 14 步）——这就是 O(log n) 的特点：数据翻多少倍， 步数只加一点点。所以二分查找能轻松对付"天文数字"级别的数据。

下一课预告：老师说："作业本找得快是本事，可'排好序'三个字 才是前提！我们班的成绩单乱成一锅粥，谁帮我把它排好？" 排序算法登场——第一个出场的，是最直观的"泡泡排队"。