关于java:LeetCode278第一个错误的版本

第一个谬误的版本

题目形容：你是产品经理，目前正在率领一个团队开发新的产品。可怜的是，你的产品的最新版本没有通过品质检测。因为每个版本都是基于之前的版本开发的，所以谬误的版本之后的所有版本都是错的。

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

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

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：二分法

别离用low和high记录第一个元素和最初一个元素，而后用二分法求解，求解过程如下：

• 用mid记录两头地位，即low + (high - low) / 2，而后调用isBadVersion(mid)办法判断以后版本是否是谬误版本；
• 如果以后版本是谬误版本且以后版本后面的一个版本(须要再次调用isBadVersion办法)也是谬误版本，则将high重置为mid-1，而后进行下一轮解决；
• 如果以后版本是谬误版本然而以后版本的后面一个版本不是谬误版本，则以后版本即是第一个谬误版本，返回以后版本；
• 如果以后版本不是谬误版本，则将low重置为mid+1，而后进行下一轮解决。
• 循环终结的条件就是low大于high。

最初，如果没有找到谬误的版本，返回-1。

public class LeetCode_278 extends VersionControl {
    /**
     * 二分法
     *
     * @param n
     * @return
     */
    public static int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isBadVersion(mid)) {
                if (mid > low && isBadVersion(mid - 1)) {
                    high = mid - 1;
                } else {
                    return mid;
                }
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(firstBadVersion(2126753390));
    }
}

class VersionControl {
    /**
     * 测试数据，前1702766718个版本都不是谬误版本，从第1702766719个版本开始都是谬误版本
     */
    public static boolean isBadVersion(int version) {
        if (version < 1702766719) {
            return false;
        } else {
            return true;
        }
    }
}

【每日寄语】 如果胜利有捷径，那条路肯定是保持。