二分法表面上看很简单，但历经千辛万苦才出现了史上第一个没有bug的二分法代码。虽然我们在日常工作中不使用手写二分法，但它的思想非常有用，例如排查master分支上有问题的提交。场景一般而言，master分支上的代码需要没有bug，可以发布。但是在实际的工作场景中，每次commit都要做严格的ab测试和验证是非常麻烦的。有时候，只改一行代码，改动很小，直接合并到master。假设我们每周修复一次线路，master上已经累积了十几个提交。直接把最新的commit全量上线，可能会引入问题：业务指标参差不齐，耗时参差不齐，错误率参差不齐……所以想办法把这些commit安全的推上线，找到有问题的commit。原理假设有1000个实例在线，50个实例作为basegroup，50个实例作为abtestgroup，即10%的流量用于ab实验。前者是benchmark，以this为标准，如果abtest组达标了，就认为没问题。master分支上图中C0代表项目第一次提交，C100代表当前在线运行的版本。C101到C110是过去一周的变化，我们的目标是将C110全部推上线。问题是C101->C110之间可能存在一些有问题的提交，任务是找到这个提交。我们将C100部署到base组，将C110部署到abtest组，上线跑了一天。ab实验通过收集各种业务指标、服务指标、工程指标等来比较两个版本的差异，如果发现base组和abtest组的指标基本一致，说明中间的版本C101->C110没有问题，安全。然后就可以直接push所有的C110了；否则说明中间有一个有问题的commit，然后用二分法定位。总之，我们需要一个可以做ab实验的系统，一个可以比较各种指标的系统。实践明白原理，实践起来比较简单。但是中间还是有一些稍微绕口的地方，如果不深挖的话，很可能会漏掉这些细节。第一次做大跨度的ab实验：当前线上版本（C100）->master上最新版本（C110），包括多次commit，发现指标参差不齐，说明有问题的commit是这里之间。然后中间选一个版本C105，打开一个ab：C105->C110，发现有问题；同时开一个C100->C105的ab，没有问题。说明一直到C105都没有问题，C105成为最新的安全版本。然后又开了一个ab：C105->C107，如果此时基组用C106就不行了。因为之前的实验只能说明C105没有问题，不代表C106没有问题。也就是说，C100安全传递给C105安全。继续打开C107->C110...总结一下规律：整个过程就是通过二分查找不断扩大安全版本范围和缩小问题版本范围的过程。首先有一个已知的安全版本（通常是在线运行的版本）作为基础，然后对方往外迈出一大步，通常是最新的提交；这次的ab实验一般都是有问题的，否则后面的二分查找就没有了。然后找一个中间的版本，开两个abs：start->mid，mid->end。如果运气好，可以排除start->mid，安全范围会迅速扩大。然后同样的思路，递归下去。小结本文描述了一个使用二分法验证master分支的commit是否在线的过程。其中一个重点是，当确定mid没有问题的时候，下次应该以mid为起点，不能使用mid+1。因为mid被证明是安全的，可以作为base，所以不代表mid+1也是安全的。言外之意是base免检，其他commit也应该作为检查对象。进一步抽象：给定一个包含0和1的数组，1占多数，代表好的提交，0代表有问题的提交，我们需要找到其中的0。最简单的方法是一个一个地搜索。线性搜索的复杂度为O(n)，采用二分查找的方法将其降低为O(logN)以加快速度。
