小探险家学算法

Appearance

10. 大海捞针（线性查找） ​

知识点：线性查找 —— 从头到尾挨个找（O(n)）

项目：在一堆作业本里找到"小明的作业本"

故事开场：作业本堆成了山 ​

下课后，讲台上堆了一摞作业本。老师说："帮我把'小明'的作业本找出来。"

你走到讲台前，从最上面一本开始翻："小雨……不是。小刚……不是。 小明！找到了！"

这就是最自然的找法：从头到尾，一本一本翻，翻到为止。

现在老师加码了："如果我叫你找'小华'的作业本，而小华今天请了假、 根本没交作业呢？"

你愣住了："那……我得把整摞作业本全部翻完，才能确定他没交。"

老师点点头："这就叫'大海捞针'——你找到了针，很幸运； 找不到，也得把整个大海捞完才敢说没有。我们把这种找法写成程序吧。"

笨办法先行：先会写，再谈快慢 ​

"从头到尾挨个找"听起来简单，写起来也确实简单——一个循环的事：

ts
// 作业本堆（上面是第 0 本，往下翻）
const books = ["小雨", "小刚", "小明", "小丽", "小红"]

// 找一本作业本：从第 0 本开始翻，翻到为止
function findBook(name: string): number {
  for (let i = 0; i < books.length; i++) {
    if (books[i] === name) {
      return i          // 找到了！返回它是第几本（从 0 开始数）
    }
  }
  return -1             // 翻完了也没找到，返回 -1（表示"没有"）
}

console.log("小明的作业本在第 " + findBook("小明") + " 本")
console.log("小华的作业本：" + findBook("小华"))

输出：

小明的作业本在第 2 本
小华的作业本：-1

能跑，而且逻辑清清楚楚。但是——老师开始加码了：

"全校有 100 万个同学的名字，都存在程序里。请你帮我找'同学999999'。 而且，你要把它放在一本 5000 页的字典里，就像在字典里找一个字， 从第一页翻到最后一页。"

引出知识点：线性查找——O(n)，一个接一个 ​

这种"从头到尾，一个接一个找"的办法，有个正式的名字，叫 线性查找（linear search）。线性，就是"一条线"——像排队一样， 沿着这条线从第一走到最后。

它的速度，我们在第 1 章就认识过了：

O(n)——有 n 个东西，最坏要翻 n 次。 数据翻一倍，时间也翻一倍。

  • 10 本作业本：最坏翻 10 次
  • 100 万本：最坏翻 100 万次
  • 而且如果目标不存在（像请假没交作业的小华）， 一定是把全部翻完才能确定——永远是最坏的情况！

线性查找的优点是简单：数据没排过序也能找， 数组、链表上都能用（还记得链表吗？链表没有编号， 找第 k 个只能一节节数——那本质上就是线性查找！）。 缺点是慢：数据一大，就真的变成"大海捞针"了。

跑起来：看看"大海"有多大 ​

我们把 100 万个号码牌放进程序，然后找最后一个——最坏的情况：

ts
// 100 万个号码牌
const cards: number[] = []
for (let i = 1; i <= 1000000; i++) {
  cards.push(i)
}

// 找"1000000"号：要翻到最后一个才能找到
console.time("找 100 万个数里的最后一个")
let result = -1
for (let i = 0; i < cards.length; i++) {
  if (cards[i] === 1000000) {
    result = i
  }
}
console.timeEnd("找 100 万个数里的最后一个")
console.log("找到了：" + result)

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

找 100 万个数里的最后一个: 3ms

100 万次比较，3 毫秒——听起来还挺快的？

那我们做个小实验：把 1000000 全改成 100000（10 万），再跑一次。 你会发现耗时变成 0.3 毫秒左右。

看到了吗？数据变 10 倍，时间也变 10 倍——这就是 O(n) 的"指纹"。 如果数据变成 10 亿（全校查重、全网找名字），时间就要乘以 1000， 变成好几秒。而在真正的程序里，几秒可能就是"卡死"了。

小挑战 ​

  1. 找第一个和最后一个：改一改 findBook，让它返回"小丽"的作业本 在第几本（我们已经做了）……再写一个新函数，找最后一个叫"小明" 的作业本（提示：不急着返回，继续翻，记住最后一次找到的位置）。
  2. 有没有"小明"？：写一个 hasBook(name) 函数，只回答"有没有"， 返回 true 或 false（提示：找到了就 return true，翻完没有就 return false）。
  3. 数一数：统计作业本堆里共有几本（提示：这不就是遍历数组， 数 books.length 嘛——遍历本身就是 O(n) 的活儿）。

课后练习 ​

第 1 题（动手题）：找最高分 ​

一个班 10 个同学的成绩都存在数组里，写一个函数找到最高分。 （提示：从第 1 个开始，遇到比当前最高的更高的，就更新"当前最高"。）

参考答案（点开查看）
ts
const scores = [78, 92, 65, 88, 70, 95, 60, 82, 90, 73]

function findMax(list: number[]): number {
  let best = list[0]            // 先假设第 1 个是最高分
  for (let i = 1; i < list.length; i++) {
    if (list[i] > best) {
      best = list[i]            // 遇到更高的，更新
    }
  }
  return best
}

console.log("最高分是：" + findMax(scores))   // 95

这其实也是在"找"——只不过找的是"最大的那个"。遍历一遍，O(n)， 这是所有"找最值"问题的通用解法。

第 2 题（思考题）：为什么找不到时最倒霉？ ​

线性查找里，如果目标不在数组里，程序要花多长时间？和 "目标恰好在第 1 个"相比呢？

参考答案（点开查看）

目标不在数组里 → 必须把 n 个元素全部检查一遍才能确定 → 永远是最坏情况 O(n)。

目标在第 1 个 → 第 1 次就找到了 → 最快情况 O(1)（只要一步）。

所以线性查找是"运气好就快，运气差就慢"的算法。平均来说， 要翻大约 n ÷ 2 次（还是 O(n) 量级）。我们给这种"最坏情况"起了名字， 叫最坏时间复杂度——评价算法时，我们永远按最坏情况算， 这样程序在最倒霉的时候也不会超时。

第 3 题（思考题）：排好序就不一样了 ​

老师把全班作业本按名字的编号排好再让你找。你能想到什么办法， 比"从第一本翻起"更快？——答案我们下一章揭晓。

参考答案（点开查看）

（这是下一章的预告题，现在想不出来也没关系。）

提示：如果作业本按编号排好了，"小明"一定在编号比它小的名字和 编号比它大的名字之间。那我们可以先翻中间那一本，看看目标 在它的前面还是后面——一次就能排除掉一半！下一章《猜数大师》 就讲这个办法，它叫二分查找，只需要 O(log n) 步。 还记得第 1 章的猜数字游戏吗？

下一课预告：作业本排好序了。这次我们不从第一本翻起——先翻中间！ "小明"比中间那本靠前？那后半摞直接不用看了。一次排除一半， 100 万本作业本，最多翻几次？答案会让你吃惊。