二分查找：猜数字游戏的最优解
玩一局 1 到 100 猜数字，体会每猜一次范围砍一半；十亿条数据 30 次就能找到——log n 快到什么程度
本页解决的问题
先给结论「二分查找：猜数字游戏的最优解」要解决的关键问题是什么？
玩一局 1 到 100 猜数字，体会每猜一次范围砍一半；十亿条数据 30 次就能找到——log n 快到什么程度
让这个结论先证明自己值得留下。 把这一页当成决策工具，而不是需要背下来的定义。把概念连到一个真实任务、一个可观察结果，以及一个能改变你判断的失败上。
写下一个问题：试完这个方法后，你能用什么证据回答它？
结论听起来很完整，却没有检查最关键的假设。
系统已经想好了一个 1 到 100 之间的数。下面的条带就是全部候选：点任意数字开猜，我会告诉你大了还是小了，被排除的数字会自动变灰。先按直觉乱猜一局记下次数，再点「按二分猜」看标准答案。留意：二分每猜一次，亮着的区域正好砍掉一半。
「砍一半」的威力在数据大的时候才真正显灵。点下面的数据量，看二分最多要猜几次，再看那条「连续对折」的动画。留意：数据量翻一万倍，次数只是从 7 涨到 20 出头。
⚠️ 重要前提：二分的门票是「先排好序」
猜数字游戏能玩，是因为数字天然有大小顺序——「大了」这个提示才有意义。换成一本页码被打乱的字典，翻到中间发现是「猫」，你完全不知道「狗」在左边还是右边，二分当场失效。所以想享受 O(log n) 的查找，得先付出排序的成本——排序怎么做、贵不贵，正是下一课的主角。
翻字典 / 翻通讯录
找「王」不会从第一页翻起：先翻到中间，比一下拼音前后，直接扔掉一半——你手上的动作就是二分。
git bisect 找坏提交
1000 个提交里有一个引入了 bug？git 帮你自动跳到中间的提交测一下，好的砍前半、坏的砍后半，10 次内锁定元凶。
猜价格 / 调参数
「这瓶酒多少钱？」「高了」「低了」——综艺里的猜价环节，高手全在心里做二分。调试超参数时的手动逼近也是同款。
「交互一 · 猜数字游戏」里的算法代价曲线
「系统已经想好了一个 1 到 100 之间的数。下面的条带就是全部候选： 点任意数字开猜 ，我会告诉你大了还是小了，被排除的数字会自动变灰。先按直觉乱猜一局记下次数，再点「按二分猜」看标准答案。」真正训练的不是背诵步骤，而是识别重复工作：输入变大时，程序到底多做了多少次比较、移动或递归。
先找重复工作，再谈快慢
「「砍一半」的威力在数据大的时候才真正显灵。点下面的数据量，看二分最多要猜几次，再看那条「连续对折」的动画。」可以拆成输入规模、每轮做什么、以及是否能缩小下一轮范围三个问题。Big-O 是描述增长趋势的语言，不是对每台机器的精确计时；常数、内存和真实数据分布也会影响最终结果。
- 砍一半的威力 ：100 个候选 7 次，十亿个候选也只要 30 次——这就是 O(log n)
- 不靠运气，靠保证 ：二分给的是最坏情况的上限，工程要的就是确定性
- 有序是前提 ：乱序的字典没法翻，想用二分先付排序的钱（下一课）
别把理论最优当成无条件最优
面对 AI 写出的算法，先用小输入手算一遍，再用逐渐放大的数据做基准测试。这样才能把「「这瓶酒多少钱？」「高了」「低了」——综艺里的猜价环节，高手全在心里做二分。调试超参数时的手动逼近也是同款」从一句结论变成可检查的性能判断。
从「交互一 · 猜数字游戏」走到「交互二 · 十亿条数据只要 30 次」
「交互一 · 猜数字游戏」先把问题落在「系统已经想好了一个 1 到 100 之间的数。下面的条带就是全部候选： 点任意数字开猜 ，我会告诉你大了还是小了，被排除的数字会自动变灰。先按直觉乱猜一局记下次数，再点「按二分猜」看标准答案。 留意：二分每猜一次，亮着的区域正好砍掉一半」上；到了「交互二 · 十亿条数据只要 30 次」，讨论继续推进到「「砍一半」的威力在数据大的时候才真正显灵。点下面的数据量，看二分最多要猜几次，再看那条「连续对折」的动画。 留意：数据量翻一万倍，次数只是从 7 涨到 20 出头」。两段连起来，重点就不只是记住一个结论，而是看清它成立所依赖的条件。
把这条判断带到下一个场景
算法题换成真实任务后，先找出重复工作，再问输入规模如何变化，最后用一个小基准验证理论判断。这样不会把复杂度记成脱离场景的标签。
- 「交互一 · 猜数字游戏」：系统已经想好了一个 1 到 100 之间的数。下面的条带就是全部候选： 点任意数字开猜 ，我会告诉你大了还是小了，被排除的数字会自动变灰。先按直觉乱猜一局记下次数，再点「按二分猜」看标准答案。 留意：二分每猜一次，亮着的区域正好砍掉一半
- 「交互二 · 十亿条数据只要 30 次」：「砍一半」的威力在数据大的时候才真正显灵。点下面的数据量，看二分最多要猜几次，再看那条「连续对折」的动画。 留意：数据量翻一万倍，次数只是从 7 涨到 20 出头
- 「最后的要点」：日常真身 ：翻字典、git bisect 找坏提交、猜价格，全是二分
最后的「最后的要点」把讨论落到「日常真身 ：翻字典、git bisect 找坏提交、猜价格，全是二分」。回看这条线索时，最值得保留的是：当输入、规模或风险改变，哪些判断需要重新做一遍。
✅ 这一课想和你分享的
- 砍一半的威力：100 个候选 7 次，十亿个候选也只要 30 次——这就是 O(log n)
- 不靠运气，靠保证：二分给的是最坏情况的上限，工程要的就是确定性
- 有序是前提：乱序的字典没法翻，想用二分先付排序的钱（下一课）
- 日常真身：翻字典、git bisect 找坏提交、猜价格，全是二分
我把这篇文章里的一个判断改写成了今天可以验证的小实验。比记住结论更有用的是，知道下一步要观察什么。
读完以后我先回头找它成立的条件，而不是直接把方法搬进项目。这个顺序让后面的取舍清楚很多。
如果把这个判断放到真实工作里，最先需要补的约束是什么？我想知道从阅读到第一次实践之间，哪一步最值得先做。
还没有这篇文章的讨论。