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