漫画：如何使用二分法回滚代码？
01 PART
First Bad Version
一般我们使用 git reset --hard #version 来进行回滚到指定版本的代码。
第278题：假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
02 PART
推导过程
这个题目还是相当简单的....我拿出来讲的原因，是因为我的开发生涯中，真的遇到过这样一件事。当时我们做一套算薪系统，算薪系统主要复杂在业务上，尤其是销售的薪资，设计到数百个变量，并且还需要考虑异动（比如说销售A是团队经理，但是下调到B团队成为一名普通销售，然后就需要根据A异动的时间，来切分他的业绩组成。同时，最恶心的是，普通销售会影响到其团队经理的薪资，团队经理又会影响到营业部经理的薪资，一直到最上层，影响到整个大区经理的薪资构成）要知道，当时我司的销售有近万名，每个月异动的人就有好几千，这是非常非常复杂的。然后我们遇到的问题，就是同一个月，有几十个团队找上来，说当月薪资计算不正确（放在个人来讲，有时候差个几十块，别人也是会来找的）最后，在一阵漫无目的的排查之后，我们采用二分的思想，通过切变量，最终切到错误的异动逻辑上，进行了修正。
回到本题，我们当然可以一个版本一个版本的进行遍历，直到找到最终的错误版本。但是如果是这样，还讲毛线呢。。。
//JAVA
public int firstBadVersion(int n) {
for (int i = 1; i < n; i++) {
if (isBadVersion(i)) {
return i;
}
}
return n;
}
我们自然是采用二分的思想，来进行查找。举个例子，比如我们版本号对应如下：
如果中间的mid如果是错误版本，那我们就知道 mid 右侧都不可能是第一个错误的版本。那我们就令 right = mid，把下一次搜索空间变成[left, mid]，然后自然我们很顺利查找到目标。
根据分析，代码如下：
//JAVA
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
额外补充：
- 请大家习惯这种返回left的写法，保持代码简洁的同时，也简化了思考过程，何乐而不为呢。
当然，代码也可以写成下面这个样子（是不是感觉差点意思？）
//JAVA
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
int res = n;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (isBadVersion(mid)) {
res = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return res;
}
}
郑重申明（读我的文章必看）：
- 本系列所有教程都不会用到复杂的语言特性，大家无须担心没有学过相关语法，算法思想才是最重要的！
- 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode进行过测试运行。
03 PART
杂谈
据查，医书有服用响豆的方法，响豆就是槐树果实在夜里爆响的，这种豆一棵树上只有一个，辨认不出来。取这种豆的方法是，在槐树刚开花时，就用丝网罩在树上，以防鸟雀啄食。结果成熟后，缝制许多布囊贮存豆荚。夜里用来当枕头，没有听到声音，便扔掉。就这么轮着枕，肯定有一个囊里有爆响声。然后把这一囊的豆类又分成几个小囊装好，夜里再枕着听。听到响声再一分为二，装进囊中枕着听。这么分下去到最后只剩下两颗，再分开枕听，就找到响豆了。
前三章的题目，都是比较简单的，目的是让大家对二分能有一些深层次的思考。从明天开始，我就会增大难度，为大家讲解一些，不那么容易可以直接想到使用二分法进行求解的题目，希望大家支持！