对半切分：64 个版本只需六次判定
一句话总结
二分查找不是工具，而是一套流程。只要让机器能够判定好与坏，64 个构建的历史和 4096 行数据，就能分别缩减为六次和十二次。
为什么需要它
在现场，最常听到两句话：“上周之前还是好的”和“只有昨天进来的文件会崩”。这两句听起来完全不同，结构却是一样的：某处有一条边界，边界之前是好的，边界之后是坏的。我们要找的就是这条边界。
找边界最自然的方法，是从头开始逐个查看。逐个运行 64 个构建，最坏情况要 64 次，如果每次耗时 30 秒，就是 32 分钟。把 4096 行数据一行一行地放进去试，就要 4096 次。而客户方的负责人还在旁边等着。
每次对半切分，数字就变了。候选是 63 个时为六次，4096 个时为十二次，即使是 100 万个也只要二十次。候选每翻一倍，增加的次数只有一次。这个性质改变了现场工作的性质——数据越大，与顺序查找的差距只会越拉越大。
工作原理
二分查找要成立，需要三个条件。
第一，必须能由机器来判定。“看起来有点奇怪”不是判定。判定器必须是一个接收输入、给出好或坏两种结果之一的程序，如果掺入人看着屏幕歪头思考的环节，就没法重复二十次。git bisect 之所以采用 git bisect run <스크립트>（占位符为脚本）这种形式，原因就在这里。按照这个约定，退出码 0 表示好，1 到 124 之间表示坏，125 表示无法判断（跳过）。本实验也使用同样的约定。
第二，性质必须是单调的。边界之前全部是好的，边界之后全部是坏的。如果历史中曾经修好后又坏掉，二分查找给出的就不是“第一个变坏的构建”，而是“某个坏的构建”。数据方面也一样。一行就能单独弄崩程序的情况是单调的；但只有两行同时存在才会崩的情况不是单调的，一旦切分，两行就会被拆开，两边都能通过。
第三，候选必须有顺序。构建有时间顺序，文件有行顺序。没有顺序的候选（二十个配置项），不能做二分，而是分组后每次关掉一半，用的是同样的原理。
Python 标准库的 bisect 模块提供了在有序数组中查找值位置的函数。我们做的是调用判定器的查找，而不是在数组中查找，骨架是一样的。把已知好的位置设为 lo，已知坏的位置设为 hi，不断询问中间位置并拉近其中一端，直到两者之间只剩一格。候选有 n 个时所需的询问次数是向上取整的 log2(n)——每询问一次候选就减半，要把 n 变成 1，只需数一数 2 要乘多少次才等于 n。
후보 63개 → 6번 후보 4096개 → 12번
후보 100만개 → 20번 후보 10억개 → 30번
无法判断是一个特殊的值。无法启动的构建、缺少依赖模块的构建、只有那天网络挂了的构建，都属于这一类。如果把它算作“坏”，边界就会向前推移，错误地把别的构建指认为元凶。所以要设第三个值，遇到它就向相邻的构建挪一格重新询问。如果整个区间都无法判断，就不要指认某一个构建，而是原样报告剩余的区间。缩小范围同样是成果。
在现场相遇的样子
第一，在做出判定器之前就开始查找。运行中间的构建，一边说“嗯，好像有点慢”，一边凭眼睛判定，过了十次左右，自己都记不清哪一边说过是好的了。先做出判定器，查找就只是一个循环。
第二，找到了边界却不去验证。查找是对数级的，但验证是线性的。把边界之后的构建全部运行一遍，确认是否全是坏的，所需成本与一开始就做顺序查找相同。尽管如此，也必须做一次——因为在非单调的历史中，二分查找会悄悄地给出错误答案。如果时间不够，至少要确认边界构建是坏的，以及它之前的构建是好的，共两次。
第三，在数据一侧二分时弄丢了表头。把 CSV 对半切分时如果去掉表头，后半部分的片段会把第一行当作列名，从而莫名其妙地失败。于是所有片段都变成了坏，查找就指向第 1 行。制作片段时，必须始终带上表头。
第四，不统计次数。如果报告里只写“用二分查找找到了”，客户就不知道这套流程的价值。如果写“把 4096 个候选用 12 次缩小了范围”，就会有人提出下次也用同样的流程。数字会把方法推销出去。
实际工作中真正重要的事
- 判定器优先。机器无法分辨好与坏，查找就无法开始。
- 不要把无法判断折算成坏。设第三个值，向相邻的构建绕开。
- 怀疑单调性。找到边界之后至少确认两次，可能的话做全量验证。
- 记录次数。如果用顺序查找会是多少次，也要一并写下，流程才推销得出去。
下一项实验要做什么
手里拿着客户的 64 个构建和新的 4096 行输入，先做出区分好、坏和无法判断的判定器。用这个判定器把历史对半切分，找出第一个变坏的构建，并加上遇到无法启动的构建时绕开的路径。把同样的原理应用到数据上，用十二次找出让加载器崩溃的那一行，再全量验证边界是否真的是边界，最后连同用顺序查找会是多少次，一起汇总成一页纸进行报告。