二分查找：为什么敢跳过一半 上线以来的每一次修改，新的在前。
按视频讲述重写二分查找，文章保留回看说明
标题从「二分查找：为什么能一次少找一半」改成「二分查找：为什么敢跳过一半」
增加 4211 字，删去 2976 字
一张有 15 个价格的表，想确认里面有没有 81 元。从头挨个看，要看到第 11 个。这次换个办法：只看 55、93、72、81，四轮就找到。
## :cite[55 都小了，左边更不用看]{b=kzsdw6kx}
省下来的动作，来自一个条件：:cite[价格已经按从小到大的顺序排好]{b=kzsdw6kx}。看过中间的价格，就能判断一整边都不可能是答案。
:::notes
我们要在一张价目表里找八十一元。表里有十五个价格，从头挨个看，要看到第十一个。现在换个办法，只看四个位置就能找到。先记住一个条件：这张表已经按价格，从小到大排好了。
:::
## 跟着 81 元，把范围越缩越小
:::scene{title="找 81 元：15 → 7 → 3 →先看 155，左边就省了" ratio="16:9"}
```js
const values = [8, 12, 17, 23, 31, 38, 46, 55, 64, 72, 81, 93, 106, 120, 145]
const prices = values.map(value => box(String(value), { w: 44, h: 4854 }))
row(prices, { y: 205210, gap: 6 })
const targetgoal = text("目标：找 81 元", { x: 400, y: 10095, size: 2830, bold: true })
const status = text("候选范围：全部 15 个价格从小到大排好了", { x: 400, y: 300310, size: 2324 })
const hinttrail = text("从小到大排列 · 变淡的价格不再查找55 → 93 → 72 → 81", { x: 400, y: 355225, size: 1638, colorbold: "soft"true })
show(prices, targetgoal, status, hint)
step("55 元偏比 81 小；它和左边的价格全部排除，剩比 755 个更小的左半边也不可能是答案。", () => {
say("先看正中间，五十五。我们找八十一，它比五十五大。左边那些价格更小，肯定也不是八十一。所以五十五以及它左边的数，一共八个位置，都不用再看，只留右边七个。")
say("我先看中间这个，五十五。它都比八十一小了，左边那些更便宜的，还用挨个看吗？")
highlight(prices[7], { dur: 300 })
together(() => {
dimhighlight(prices.slice(0, 8)[7], { dur: 300450 })
set(status, { text: "55 < 81：排除都小了，左边，剩 7 个更小" }, { dur: 300350 })
})
})
step("剩余范围的中间是 93 元；它和右边的价格排除，剩 3 个。", () => {
say("注意，现在取的是右边这七个数的中间，不是整张表的中间。这回看到九十三，比八十一大。九十三右边只会更贵，所以从九十三往右都排除。剩下六十四、七十二、八十一。")
step("连同 55 一起排除左边八个位置，只留下右边七个。", () => {
highlight(prices[11], { dur: 300 })
say("这一边就不用看了。五十五也不是答案，一起划掉。还剩右边七个。")
together(() => {
dim(prices.slice(110, 8), { dur: 300650 })
set(status, { text: "93 > 81：排除不用看了 ← 只找右边，剩 37 个" }, { dur: 300350 })
})
})
step("72 元仍偏小；排除 64 和 72，只剩 81。", () => {
say("在剩下这三个数里，中间是七十二。它比八十一小，六十四还更小。这两个都排除，范围就缩到八十一这一个数了。")
step("在剩下的七个数里取中间，这次看到 93。", () => {
highlight(prices[9], { dur: 300 })
say("这次别再盯着整张表了。咱们只在右边这七个里面找中间。九十三，比八十一大了。")
together(() => {
dimhighlight(prices.slice(8, 10)[11], { dur: 300450 })
set(status, { text: "72 < 81：继续缩小，只在剩 81下的里面取中间" }, { dur: 300350 })
})
})
step("检查最后一个候选：81 等于目标，四轮查找结束。", () => {
say("只剩一个，也得真的比一下。现在看到的就是八十一，和目标相等，找到了。从十五个候选到七个，再到三个、一个，这一路总共看了四个中间位置。")
step("93 已经偏大，它右边更大的价格也可以排除。", () => {
say("九十三都嫌贵，它右边就更贵了。这一头也不用看。现在只剩六十四、七十二、八十一。")
together(() => {
highlightdim(prices[10].slice(11), { tone: "c2", dur: 300650 })
set(status, { text: "81 = 81还剩：找到，共检查 4 轮64、72、81" }, { dur: 300350 })
})
})
```
:::
:::notes
step("三个候选的中间是 72；72 和左边的 64 都小于目标。", () => {
看这排价格，目标是八十一元。接下来每看一个中间数，就把确定不可能的那一边变淡。灰掉只是表示不再查找，原来的数据并没有被删掉。
say("三个数，中间就是七十二。还是小了。八十一不可能躲到比七十二还小的那边去。")
:::
together(() => {
highlight(prices[9], { dur: 450 })
## “中间”说的是位置，不是平均价格
set(status, { text: "72 小了，64 也不用再看" }, { dur: 350 })
})
:cite[二分查找取的是当前范围的中间项]{b=4h9anmwj}。剩 7 个就看第 4 个，剩 3 个就看第 2 个；两端价格差多少，不影响这个选择。
})
表里的最低价是 8，最高价是 145。把它们相加再除以二得到 76.5，但表里根本没有这个价格。我们不猜一个价格，而是去看队伍中间那个真实存在的数。
step("排除 64 和 72，最后剩下的 81 仍要检查。", () => {
say("所以这两个也排掉。只剩八十一了，不过还得确认一下，不能剩谁就算谁。")
together(() => {
dim(prices.slice(8, 10), { dur: 650 })
set(status, { text: "只剩 81，还得比一下" }, { dur: 350 })
})
})
候选个数是偶数时，中间有两个位置，取靠左或靠右的都可以；本文固定取靠左的。每次缩小范围后，都要重新取中间。
step("81 与目标相等，查找成功。", () => {
say("八十一，和要找的一样。行，找到了。")
together(() => {
highlight(prices[10], { tone: "c2", dur: 450 })
set(status, { text: "81 = 81，找到了" }, { dur: 350 })
})
})
:::notes
step("四次比较就找到了目标，每次都利用顺序排除一整侧。", () => {
这里的中间，说的是站在第几个位置，不是把最便宜和最贵的价格取个平均。八块和一百四十五块的平均价是七十六块五，可表里压根没有它。我们直接去看中间那一项。范围缩小了，下次就从新的范围里取中间。
say("刚才真正拿来比较的，就这四个。每看一个，都能顺带排除一大批。这就是二分查找。")
together(() => {
hide(prices, { dur: 400 })
show(trail, { from: "fade", dur: 500 })
set(goal, { text: "15 个价格，只比了 4 个" }, { dur: 350 })
set(status, { text: "每看一个，就能少找一边" }, { dur: 350 })
})
})
```
:::
## 剩下一个，也可能没找到
把目标换成 **80 元**，还会依次看到 55、93、72、81。最后只剩 81，但 81 并不等于 80。
:cite[只有比较相等，才能报告命中]{b=q29qczfv}。81 偏大，继续排除它；候选范围变空，就明确回答“没有找到”，不能因为它离 80 最近就交差。
如果把待查范围的两端叫作左边界、右边界，那么 :cite[左边界超过右边界，就表示没有候选项了]{b=q29qczfv}。两者相等时，还剩一个位置，必须检查。
:::notes
现在把目标改成八十元。前面的判断一样，最后也会走到八十一。可八十一不是八十，离得近也不算。这个数偏大，还得排除。排完以后，范围里一个位置都不剩了，这时才能说没找到。所以只剩一个要检查，一个都没了才结束。
它们已经从小到大排好了。八块，十二块，十七块，越往右越贵。
:::
## 数据多一千倍，查找轮数只多十轮
## :cite[差一块，也不能算找到]{b=q29qczfv}
每轮检查一个中间项；只要还没找到，就排除中间项以及不可能的一侧。剩余候选数最多约为原来的一半，查找轮数因此增长得很慢。
:cite[按每轮取中间并收缩区间计算，最坏轮数如下]{b=r0mdgjn2}：
| 已排序的数据量 | 最多检查多少轮 |
:::scene{title="差一块，也不能算找到" ratio="16:9"}
|---|---|
```js
| 15 条 | 4 轮 |
const goal = text("这次找 80 元", { x: 400, y: 90, size: 32, bold: true })
| 1,000 条 | 10 轮 |
const routeText = text("55 → 93 → 72 →", { x: 305, y: 215, size: 26 })
| 1,000,000 条 | 20 轮 |
const last = box("81", { x: 555, y: 215, w: 88, h: 74, tone: "c2" })
const result = text("最后还是走到了 81", { x: 400, y: 325, size: 26 })
show(goal, routeText, last, result)
从一千条变成一百万条，数据多了一千倍，最坏查找轮数从十轮变成二十轮。这种增长方式记作 $O(\log n)$，其中 $n$ 是数据条数。
step("81 不等于 80；只剩一个候选，不代表已经找到。", () => {
say("可八十一不是八十。就差一块，也不能算找到了。")
together(() => {
highlight(last, { dur: 400 })
set(result, { text: "81 ≠ 80，差 1 也不算" }, { dur: 350 })
})
})
这里数的是“取一个中间项并判断”的轮次，**不是毫秒，也不是代码里比较符号的执行次数**。上表只计算在已排序数组里查找，预先整理数据的成本没有算进去。
step("排除 81 后候选范围为空，才能确定未找到。", () => {
say("它比八十大，还得排掉。现在一个都不剩，才是真的找不到。")
together(() => {
hide(last, routeText, { dur: 650 })
set(result, { text: "没找到", size: 38 }, { dur: 400 })
})
})
```
:::
:::notes
再看数据变多会怎样。一千条排好的数据，最坏查十轮；一百万条，最坏查二十轮。数据多了一千倍，只多查十轮。原因就是，每次都排掉一大块。这里说的十和二十，是看了几次中间项，不是运行了多少毫秒。前面把数据排好序花的时间，也得另外算。
把目标换成八十。前面还是那几步，最后也会走到八十一。
:::
## 没有排好队，就不能这样排除
## :cite[顺序一乱，就把答案找丢了]{b=kzsdw6kx}
把价格随手摆成这一排：**8、81、55、12、145**。目标还是 81，中间还是 55。
:::scene{title="顺序一乱，就把答案找丢了" ratio="16:9"}
```js
const nums = [8, 81, 55, 12, 145].map(v => box(String(v), { w: 94, h: 74 }))
row(nums, { y: 215, gap: 22 })
const goal = text("顺序打乱，还是找 81", { x: 400, y: 90, size: 30, bold: true })
const wrong = frame("照旧只查右边", { around: [nums[3], nums[4]], pad: 18 })
const status = text("81 在左边", { x: 400, y: 345, size: 27 })
show(nums, goal, status)
highlight(nums[1], { tone: "c2" })
如果照搬“目标更大，只查右边”，就只剩 12、145，反而把真正的 81 丢在了左边。问题出在排除的依据没了：:cite[乱序时，中间项不能代表左右两边的大小关系]{b=kzsdw6kx}。
step("照搬“比 55 大就往右找”，会把左边真正的 81 漏掉。", () => {
say("这时候，要是因为八十一更大，就只往右找，答案直接被你漏掉了。")
together(() => {
highlight(nums[2], { dur: 350 })
show(wrong, { from: "fade", dur: 600 })
set(status, { text: "81 明明在左边，却被跳过去了" }, { dur: 350 })
})
})
所以这里只讨论按价格排序的数组。真实场景里，如果数据还没整理、只查这一次，就要把排序成本也算上；不能只拿“二分查找最多二十轮”来判断整个方案划不划算。
step("按价格排好顺序，才能保证另一侧确实没有答案。", () => {
say("刚才能放心划掉一边，是因为价格排好了队。顺序乱了，那半边就不能随便扔。")
together(() => {
hide(wrong, { dur: 400 })
reset(nums[2], { dur: 350 })
set(status, { text: "先排好队，才有把握排除" }, { dur: 350 })
})
})
```
:::
:::notes
但这招不能用在随便摆的数据上。看这排数，中间是五十五，可八十一偏偏在它左边。你要是因为八十一更大，就只往右找，答案直接被扔掉了。能排除一边，是因为整排数有顺序。数据没排好，就没有这个保证；为了查一次先整理全部数据，整理的工夫也要算。
还有个地方容易想岔。我把价格打乱，五十五仍然在中间，八十一却跑到了左边。
:::
## 写成程序，只是在移动两条边界
## :cite[一百万条，最多看二十个]{b=r0mdgjn2}
可以把待查范围想成夹住价格表的两个书签，左边一个，右边一个。比较完当前中间项后：
- 中间项偏小，把左书签移到中间项的下一个位置。
:::scene{title="一百万条，也不用从头熬到尾" ratio="16:9"}
- 中间项偏大，把右书签移到中间项的上一个位置。
```js
- 中间项相等，返回它的位置；两个书签交错，返回“未找到”。
const left = text("表里有多少个数", { x: 235, y: 115, size: 22, color: "soft" })
const right = text("最多看几个中间项", { x: 570, y: 115, size: 22, color: "soft" })
const count = text("15", { x: 235, y: 225, size: 56, bold: true })
const checks = text("4", { x: 570, y: 225, size: 72, bold: true, color: "accent" })
const divider = line([400, 155], [400, 285])
const note = text("按已排好序的数组计算，不含排序成本", { x: 400, y: 345, size: 18, color: "soft" })
show(left, right, count, checks, divider, note)
:cite[已比较且不相等的中间项也要排除]{b=q29qczfv}。这就是边界更新里“加一”“减一”的来历：每轮都少查一些位置，不能把同一个中间项反复留下。
step("一千项的有序数组，最坏检查十个中间项。", () => {
say("放到一千条，最多看十个中间项。")
together(() => {
set(count, { text: "1,000" }, { dur: 500 })
set(checks, { text: "10" }, { dur: 500 })
})
})
拿起下一份数据，先确认它按什么字段排了序。要找的是价格，就检查价格的顺序；按商品名排好的表，不能直接拿来二分查价格。
step("一百万项最多检查二十个中间项；数据增千倍，只多十轮。", () => {
say("一百万条，最多二十个。表长了一千倍，只多找十下。每回都少一半，要看的那一截，缩得很快。")
together(() => {
set(count, { text: "1,000,000", size: 46 }, { dur: 500 })
set(checks, { text: "20" }, { dur: 500 })
})
})
```
:::
:::notes
写进程序，其实就是移动两个书签。中间数小了，左书签移到它后面；中间数大了，右书签移到它前面。中间这个数已经看过，又不是答案，就别再留下。这样范围会越来越小。下次要用这招，先确认一件事：你要找的那一列，确实已经排好了序。
有了这个顺序，表越长，省的事就越多。十五个价格，咱们最多看四个。
:::
首次发布