二分法表面上看很简单，但历史上出现第一个没有 bug 的二分法代码还颇费了一番工夫。虽然我们在日常工作中不用手写二分法，但它的思想却很有用，例如用于排查 master 分支上有问题的 commit。

场景

通常来说，master 分支上的代码需要保证没有 bug，随时能够发布。但在实际的工作场景中，为每个 commit 做严格的 ab 测试、验证是很麻烦的事情。有时候，只改一行代码，改动非常小，直接就合入 master 了。

假设我们每周固定上一次线，master 上已经积累了十几个 commit 了。直接全量上线最新的 commit 可能会引入问题：业务指标不平、耗时不平、错误率不平……

因此要想办法能将这些 commit 安全地推上线，找到其中有问题的 commit。

原理

假设线上有 1000 个实例，拿出 50 台作为 base 组，50 台作为 abtest 组，也就是拿 10% 流量来做 ab 实验。前者就是基准，以这个为标准，如果 abtest 组符合标准，那就认为其没问题。

在上面这张图中，C0 代表项目的第一个提交，C100 代表当前线上正在跑的版本。C101 到 C110 是一周以来所做的变更，我们的目标是将 C110 推全到线上。

问题是 C101 -> C110 之间可能存在一些有问题的 commit，任务就是找到这个 commit。

我们将 C100 部署到 base 组，将 C110 部署到 abtest 组，线上跑一天时间。

通过收集各种业务指标、服务指标、工程指标等，来比较两个版本间的差异。

如果我们发现 base 和 abtest 组的指标基本一致，说明 C101->C110 中间的版本没有问题，是安全的。那就可以直接推全 C110；否则，说明中间存在有问题的 commit，接下来就用二分法来定位。

总之，我们需要一个可以做 ab 实验的系统、一个可以比较各种指标的系统。

做法

理解了原理，做法就比较简单了。但这中间还是有一些稍微有点绕的地方，如果不深入研究一下，很可能会错过这些细节。

第一次先做个大跨度的 ab 实验：当前线上的版本（C100） -> master 上最新的版本（C110），将多个 commit 包括进来，发现指标不平，说明有问题的 commit 就在这个之间。

再在中间选择一个版本 C105，开一个 ab：C105->C110，发现有问题；同时，开一个 C100->C105 的 ab，没有问题。说明到 C105 为止都没有问题，C105 成为最新的安全版本。

接着又开了一个 ab：C105->C107，如果这时 base 组用的是 C106，其实是不行的。因为前面的实验只能说明 C105 没有问题，并不能说明 C106 没问题。即 到 C100 安全传递到了 到 C105 安全。

再继续开 C107->C110……

总结规律：整个过程就是一个通过二分查找不断扩大安全版本范围，缩小问题版本范围的过程。

首先有一个已知的安全版本（通常是线上正在跑的版本），这个作为 base，然后另一侧先往外探一大步，通常是最新的提交；这一次 ab 实验 通常是有问题的，不然也没有接下来的二分查找。

接着在中间找一个版本，分别开两个 ab：start->mid，mid->end。运气好的话，start->mid 可以排除，那么安全范围会迅速扩大。然后是同样的思路，递归做下去。

总结

本文描述了一个如何用二分法检验 master 分支未上线 commit 的过程。

其中有一个关键的点是当确定了 mid 没问题时，下一次要以 mid 为起点，不能用 mid+1。因为 mid 被证明安全，可以作为 base，不能说明 mid+1 也安全。言外之意是 base 是免检的，其他 commit 都应该作为待检对象。

进一步抽象一下：给定一个包含 0 和 1 的数组，1 占多数，代表没问题的 commit，0 则代表有问题的 commit，需要找到其中的 0。

最简单的办法是一个个地找，线性找的复杂度是 O(n)，改用二分查找法降为 O(logN)，加快速度。