278. First Bad Version

Leetcode 问题: 278. First Bad Version
Categories:
Tags:

题目

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

产品坏掉了，要找出第一个坏掉的产品版本号，会传入现在 所有的版本号 n

每个版本号都是排序后的 整数 版本号，第一个坏掉的版本号后面的版号都代表都是坏的，所以要找出第一个坏掉的版本号在哪

[好, 好, 好, 坏, 坏]

有一个内部的 isBadVersion() 函式可以呼叫，传入版本号会回传传入的版号是不是坏掉的，坏掉就回传 true，好的就回传 false

Example

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Input: n = 1, bad = 1
Output: 1

演算法

1. 二分法切割要检查的数字索引范围

设定左右指标，匡选检查的范围

  • 左边指标: 0，数字阵列最左方索引
  • 右边指标: 数字阵列最右方索引，全部的版本号数字

取左右指标索引，左右逼近到可能出现的最接近的数字，如果「左边数字索引」与「右边数字索引」没有相交，表示还可以再寻找

将数字索引位置切割成一半，拿左右字母索引的平均数当作切割点，可以把数字切割成一半，减少要检查的范围

2. 检查「中间指标」确认是否是坏掉的版本号

状况 A. 如果「中间指标」位置的版本是「坏的版本号」

表示「右边」全部都是「坏的版本号」

所以「左边」有可能有好的及坏的版本，必须再检查「左边」版本号，「右边都坏的」不需要检查

将「右指标」设定为目前的「中间指标」，再继续检查

状况 B. 如果「中间指标」位置的版本是「好的版本号」

表示「左边」全部都是「好的版本号」

所以「右边」有可能有好的及坏的版本，必须再检查「右边」版本号，「左边都好的」不需要检查

将「左指标」设定为目前的「中间指标」，再继续检查

3. 确认坏的版本号位置在左指标位置

因为「左指标」会不断地往右移动，然后一直确保「左指标」的左边一定是好的版本号

所以最后左指标指定的数字，为第 1 个坏掉的版本号

答案

JavaScript

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
    return function (totalVersionNumber) {
        // 左指标
        var leftPointer = 0;
        // 右指标
        var rightPointer = totalVersionNumber;
        while (leftPointer < rightPointer) {
            // 当「左指标」还没超过「右指标」，表示还没比完，可以继续比较
            // 将检查的指标切半，用「中间指标」当作参考指标
            var middlePointer = leftPointer + Math.floor((rightPointer - leftPointer) / 2);
            // 检查「中间指标」确认是否是坏掉的版本号
            if (isBadVersion(middlePointer)) {
                // 如果「中间指标」位置的版本是「坏的版本号」，表示「右边」全部都是「坏的版本号」
                // 所以「左边」有可能有好的及坏的版本，必须再检查「左边」版本号，「右边都坏的」不需要检查
                // 将「右指标」设定为目前的「中间指标」，再继续检查
                rightPointer = middlePointer;
            }
            else {
                // 如果「中间指标」位置的版本是「好的版本号」，表示「左边」全部都是「好的版本号」
                // 所以「右边」有可能有好的及坏的版本，必须再检查「右边」版本号，「左边都好的」不需要检查
                // 将「左指标」设定为目前的「中间指标」，再继续检查
                leftPointer = middlePointer + 1;
            }
        }
        // 因为「左指标」会不断地往右移动，然后一直确保「左指标」的左边一定是好的版本号
        // 所以最后左指标指定的数字，为第一个坏掉的版本号
        return leftPointer;
    };
};

TypeScript

/**
 * The knows API is defined in the parent class Relation.
 * isBadVersion(version: number): boolean {
 *     ...
 * };
 */

var solution = function(isBadVersion: any) {

    return function(totalVersionNumber: number): number {
        // 左指标
        let leftPointer: number = 0;
        // 右指标
        let rightPointer: number = totalVersionNumber;

        while (leftPointer < rightPointer) {
            // 当「左指标」还没超过「右指标」，表示还没比完，可以继续比较
            // 将检查的指标切半，用「中间指标」当作参考指标
            let middlePointer = leftPointer + Math.floor((rightPointer - leftPointer) / 2);

            // 检查「中间指标」确认是否是坏掉的版本号
            if (isBadVersion(middlePointer)) {
                // 如果「中间指标」位置的版本是「坏的版本号」，表示「右边」全部都是「坏的版本号」
                // 所以「左边」有可能有好的及坏的版本，必须再检查「左边」版本号，「右边都坏的」不需要检查
                // 将「右指标」设定为目前的「中间指标」，再继续检查
                rightPointer = middlePointer;
            } else {
                // 如果「中间指标」位置的版本是「好的版本号」，表示「左边」全部都是「好的版本号」
                // 所以「右边」有可能有好的及坏的版本，必须再检查「右边」版本号，「左边都好的」不需要检查
                // 将「左指标」设定为目前的「中间指标」，再继续检查
                leftPointer = middlePointer + 1;
            }
        }

        // 因为「左指标」会不断地往右移动，然后一直确保「左指标」的左边一定是好的版本号
        // 所以最后左指标指定的数字，为第一个坏掉的版本号
        return leftPointer;
    };
};

参考资料