如何使用二分法回滚代码？

今天是小浩算法“365刷题计划”第70天。你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的，所以我们需要回滚代码，那如何能找到错误的版本呢？

01

PART

First Bad Version

一般我们使用 git reset --hard #version 来进行回滚到指定版本的代码。

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

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

02

PART

推导过程

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

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

1//JAVA2public 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}

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

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

根据分析，代码如下：

1//JAVA2public 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//JAVA2public 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}

郑重申明（读我的文章必看）：

  • 本系列所有教程都不会用到复杂的语言特性，大家无须担心没有学过相关语法，算法思想才是最重要的！

  • 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

杂谈

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

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

赞 (0)

相关推荐