第一个错误的版本（287）

如果你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的，所以我们需要回滚代码，那如何能找到错误的版本呢？

01、题目示例

第278题：第一个错误的版本
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。


你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。


示例:

  1. 给定 n = 5，并且 version = 4 是第一个错误的版本。
  3. 调用 isBadVersion(3) -> false
  4. 调用 isBadVersion(5) -> true
  5. 调用 isBadVersion(4) -> true
  7. 所以，4 是第一个错误的版本。

02、推导过程

这个题目还是相当简单的….我拿出来讲的原因，是因为我的开发生涯中，真的遇到过这样一件事。当时我们做一套算薪系统，算薪系统主要复杂在业务上，尤其是销售的薪资，设计到数百个变量，并且还需要考虑异动（比如说销售A是团队经理，但是下调到B团队成为一名普通销售，然后就需要根据A异动的时间，来切分他的业绩组成。同时，最恶心的是，普通销售会影响到其团队经理的薪资，团队经理又会影响到营业部经理的薪资，一直到最上层，影响到整个大区经理的薪资构成）要知道，当时我司的销售有近万名，每个月异动的人就有好几千，这是非常非常复杂的。然后我们遇到的问题，就是同一个月，有几十个团队找上来，说当月薪资计算不正确（放在个人来讲，有时候差个几十块，别人也是会来找的）最后，在一阵漫无目的的排查之后，我们采用二分的思想，通过切变量，最终切到错误的异动逻辑上，进行了修正。


回到本题，我们当然可以一个版本一个版本的进行遍历，直到找到最终的错误版本。但是如果是这样，还讲毛线呢。。。

  1. //JAVA
  2. public int firstBadVersion(int n) {
  3.     for (int i = 1; i < n; i++ ) {
  4.         if (isBadVersion(i)) {
  5.             return i;
  6.         }
  7.     }
  8.     return n;
  9. }

我们自然是采用二分的思想，来进行查找。举个例子，比如我们版本号对应如下：

PNG

如果中间的mid如果是错误版本，那我们就知道 mid 右侧都不可能是第一个错误的版本。那我们就令 right = mid，把下一次搜索空间变成[left, mid]，然后自然我们很顺利查找到目标。

PNG

根据分析，代码如下：

  1. //JAVA 
  2. public int firstBadVersion(int n) { 
  3.     int left = 1; 
  4.     int right = n; 
  5.     while (left < right) { 
  6.         int mid = left + (right - left) / 2;
  7.         if (isBadVersion(mid)) { 
  8.             right = mid;
  9.         } else {
  10.             left = mid + 1;
  11.         }
  12.     }
  13.     return left;
  14. }

额外补充：


  • 请大家习惯这种返回left的写法，保持代码简洁的同时，也简化了思考过程，何乐而不为呢。


当然，代码也可以写成下面这个样子（是不是感觉差点意思？）

  1. //JAVA 
  2. public class Solution extends VersionControl {
  3.     public int firstBadVersion(int n) { 
  4.         int left = 1; 
  5.         int right = n; 
  6.         int res = n; 
  7.         while (left <= right) { 
  8.             int mid = left + ((right - left) >> 1);
  9.             if (isBadVersion(mid)) {
  10.                 res = mid;
  11.                 right = mid - 1;
  12.             } else {
  13.                 left = mid + 1;
  14.             }
  15.         }
  16.         return res;
  17.     }
  18. }

03、杂谈

据查，医书有服用响豆的方法，响豆就是槐树果实在夜里爆响的，这种豆一棵树上只有一个，辨认不出来。取这种豆的方法是，在槐树刚开花时，就用丝网罩在树上，以防鸟雀啄食。结果成熟后，缝制许多布囊贮存豆荚。夜里用来当枕头，没有听到声音，便扔掉。就这么轮着枕，肯定有一个囊里有爆响声。然后把这一囊的豆类又分成几个小囊装好，夜里再枕着听。听到响声再一分为二，装进囊中枕着听。这么分下去到最后只剩下两颗，再分开枕听，就找到响豆了。


前三章的题目，都是比较简单的，目的是让大家对二分能有一些深层次的思考。下面我就会增大难度，为大家讲解一些，不那么容易可以直接想到使用二分法进行求解的题目，希望大家支持！