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;
    };
};

參考資料