【Day 38 】2022-01-18 - 278. 第一个错误的版本

[azl397985856]

278. 第一个错误的版本

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/first-bad-version

前置知识

• 二分法

  题目描述

  
  你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

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

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

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

[yan0327]

思路： 最左二分

func firstBadVersion(n int) int {
    l,r := 0,n
    for l < r{
        mid := l + (r-l)/2
        if !isBadVersion(mid){
            l = mid+1
        }else{
            r = mid
        }
    }
    return l
}

时间复杂度O（NlogN） 空间复杂度O（1）

[yetfan]

思路 二分

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l=1
        r=n
        while l<r:
            mid = l + (r-l)//2
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1 
        return l

复杂度 时间 O(nlogn) 空间 O(1)

[tian-pengfei]

class Solution {
public:
    int firstBadVersion(int n) {
        long low = 0;

        long high = n;
        long mid = (low+high)/2;
        bool midbad =isBadVersion2(mid) ;
        bool midbad2=isBadVersion2(mid+1) ;
        while (!(!midbad&&midbad2)){
            if(!midbad2){

                  low = mid +1;
            }
            if(midbad){
               high = mid-1;
            }
             mid = (high+low)/2;
             midbad =isBadVersion2(mid) ;
             midbad2=isBadVersion2(mid+1) ;
        }
        return mid+1;
    }
    bool isBadVersion2(int version){
        if(version==0)return false;
        return isBadVersion(version);
    }};

[charlestang]

思路

经典二分法。时间复杂度 O(logn)

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left = 1
        right = n
        while left <= right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

[MonkofEast]

278. First Bad Version

Click Me

Algo

1. Bi-Search is not that fixed. The trick is find a correct while condition and a set of correct (l, r) updating operation

Code

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l < r:
            mid = l + (r - l) // 2
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1
        return l

Comp

T: O(logN)

S: O(1)

[zwx0641]

public class Solution extends VersionControl { public int firstBadVersion(int n) { int l = 0, r = n; while (l <= r) { int m = l + (r - l) / 2; if (isBadVersion(m)) { r = m - 1; } else { l = m + 1; } } return l; } }

[laofuWF]

# binary search:

# time: O(logN)
# space: O(1)

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """

        left = 1
        right = n

        while left < right:
            mid = left + (right - left) // 2
            if not isBadVersion(mid):
                left = mid + 1
            else:
                right = mid

        return left

[Alfie100]

LeetCode题目连接： 278. 第一个错误的版本https://leetcode-cn.com/problems/first-bad-version/

解题思路

二分。

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """

        left, right = 1, n
        while left < right:
            mid = (left+right) // 2
            if not isBadVersion(mid):
                left = mid+1
            else:
                right = mid

        return left

复杂度分析

• 时间复杂度：O(log n)。
• 空间复杂度：O(1)。

[LinnSky]

思路

二分法

代码

  var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 1, right = n

        while(left < right) {
            const mid = Math.floor(left + (right - left)/2)
            if(isBadVersion(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left   
    }

复杂度分析

• 时间复杂度O(logN)
• 空间复杂度O(1)

[ZacheryCao]

Idea

BinarySearch. If current version is bad, we update right to mid. Else we update left to mid+1. When left is larger than right we return right

Code

class Solution:
    def firstBadVersion(self, n: int) -> int:
        if isBadVersion(1):
            return 1
        i, j = 1, n
        while i<=j:
            mid = i + (j - i)//2
            if isBadVersion(mid):
                if not isBadVersion(mid-1):
                    return mid
                j = mid
            else:
                i = mid + 1
        return j

Complexity

Time: O(log N) Space: O(1)

[xinhaoyi]

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

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

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

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

思路一

相当于在00000001111111找到第一个1的位置，直接二分法查找即可

代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

//在00000001111111中找到第一个1
//二分查找即可
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // bool isBadVersion(version)
        int left = 1;
        int right = n;
        int mid = -1;
        //保证出来之后只剩一个结点
        while(left < right){
            //mid向下取整，因为二分法时，中间结点给了左边区间
            //我这里犯了错误，这样求mid会有在left和right都很大时溢出的风险
            //要写成减法，模式
            mid = left + (right - left) / 2;
            //如果是错误版本，也就是1，则在其左区间继续找
            if(isBadVersion(mid)){
                right = mid;
            }
            //如果不是错误版本则在其右区间(不包含mid)继续查找
            else{
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

[feifan-bai]

思路 1.二分查找

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l <= r:
            mid = (l+r) // 2
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[zwmanman]

The isBadVersion API is already defined for you.

@param version, an integer

@return a bool

def isBadVersion(version):

class Solution(object): def firstBadVersion(self, n): """ :type n: int :rtype: int """ l = 1 r = n

    while l <= r:
        mid = (l + r) // 2
        if not isBadVersion(mid):
            l = mid + 1
        else:
            ans = mid
            r = mid - 1

    return ans

[Yrtryannn]

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { 
            int mid = left + (right - left) / 2; 
            if (isBadVersion(mid)) {
                right = mid; 
            } else {
                left = mid + 1; 
            }
        }
        return left;
    }
}

[Yachen-Guo]

思路

二分法，重要的是在判断之后区间的更新，如果mid version is bad，那么就说明要改变右边界为mid（寻找的是第一个错误的版本，所以mid是错误的也要包含其中），否则就改变左边界，此时left = mid + 1

代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

[wangzehan123]

Java Code:

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (isBadVersion(start)) {
            return start;
        }
        return end;
    }
}

[moirobinzhang]

Code:

public class Solution : VersionControl { public int FirstBadVersion(int n) { int start = 1; int end = n;

    while (start  < end)
    {
        int mid = (end - start) / 2 + start;

        if (IsBadVersion(mid))
            end = mid;
        else 
            start = mid + 1;
    }        

    return start;
}

}

[arteecold]

经典cut wood 哈哈哈

class Solution:
    def firstBadVersion(self, n):
        l, r = 1, n
        while l <= r:
            mid = (l + r) // 2
            if isBadVersion(mid):
                # 收缩
                r = mid - 1
            else:
                l = mid + 1
        return l

O(logN)

[xj-yan]

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left + 1 < right:
            mid = (left + right) // 2
            if isBadVersion(mid): right = mid
            else: left = mid
        if isBadVersion(left): return left
        return right

Time Complexity: O(logn), Space Complexity: O(1)

[freesan44]

思路

二分

关键点

代码

• 语言支持：Python3

Python3 Code:

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left,right = 1,n
        while left <= right:
            mid = (left + right)//2
            res = isBadVersion(mid)
            if res == True:
                if mid == 1 or (isBadVersion(mid-1) == False):
                    return mid
                else:
                    right = mid
            elif res == False:
                left = mid + 1
        if left != n and isBadVersion(left)== True:
            return left
        return -1

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[CoreJa]

思路

和昨天一样的套模板即可

代码

class Solution:
    # 二分法：没什么好说的，简单题，4分钟秒了，直接套`bisect`那套二分模板
    def firstBadVersion(self, n):
        left, right = 1, n
        while left < right:
            mid = (left + right) // 2
            if not isBadVersion(mid):
                left = mid + 1
            else:
                right = mid
        return left

[cszys888]

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, end = 1, n
        while start <= end:
            mid = (start + end) // 2
            if isBadVersion(mid):
                end = mid - 1
            else:
                start = mid + 1

        return start

time complexity: O(LogN) space complexity: O(1)

[JudyZhou95]

思路

binary search

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """

        l = 1
        r = n

        while l < r:
            mid = (l+r)//2

            if isBadVersion(mid):
                r = mid
            else:
                l = mid+1
        return l

复杂度

TC: O(logN) SC: O(1)

[Alexno1no2]

简单二分

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

[zhangzz2015]

思路

• 采用比较直接的二分求解，时间复杂度为O(logn)，空间复杂度为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int firstBadVersion(int n) {
        int left =1; 
        int right =n; 
        while(left<=right)
        {
            int middle = left + (right - left)/2; 

            if(isBadVersion(middle)){
                right =  middle - 1; 
            }
            else{
                left = middle + 1; 
            }            
        }
        //  [right left]

        return left;                 
    }
};

[kite-fly6618]

思路

二分

代码

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        if (n<=1) return n
        let left = 1
        let right = n
        while(left < right) {
            const mid = Math.floor(left + (right - left) / 2);
            if (isBadVersion(mid)) {
                right= mid
            }else{
                left = mid+1
            }  
        } 
        return right     
    };
};

复杂度

时间复杂度:O(logn)
空间复杂度:O(1)

[Yark-yao]

思路

二分：利用第一个错误的版本之后的版本都是错误的特性，判断中间点是否是错误版本，若是：end=mid，否则begin=mid

代码

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

var solution = function(isBadVersion: any) {

    return function(n: number): number {
        let begin = 1,end = n
        if(isBadVersion(begin)){
            return begin
        }
        while(end-begin > 1){
            const mid = ((end-begin)>>1)+begin
            if(isBadVersion(mid)){
                end = mid
            }else{
                begin = mid
            }
        }
        return end
    };
};

复杂度

时间：O(logN) 空间：O(1)

[xjhcassy]

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (isBadVersion(mid)) {
                r = mid -1;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

打卡

[GoRedFish]

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { 
            int mid = left + (right - left) / 2; 
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1; 
            }
        }

    }
}

[Flower-F]

解题思路

二分

代码

/**
 * 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) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
      let l = 1, r = n;
      let ans = 1;
      while (l <= r) {
        const mid = l + ((r - l) >> 1);
        if (isBadVersion(mid)) {
          // 满足条件，寻找最左满足，因此收缩右边界
          r = mid - 1;
          ans = mid;
        } else {
          l = mid + 1;
        }
      }    

      return ans;
    };
};

复杂度：

时间：O(logN) 空间：O(1)

[hdyhdy]

思路： 二分法

func firstBadVersion(n int) int {
    low ,high := 1,n;
   for  low <= high{
       mid := (low + high)/2
       if isBadVersion(mid) == true {
           high = mid - 1 
       }else {
           low  = mid + 1
       }
   }
    return low 
   }

时间复杂度：O(logn) 空间复杂度：O（1）

[Tesla-1i]

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l <= r:
            mid = (l+r) // 2
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

[nonevsnull]

思路

//s6

• 思路与解法

• 二分就是模版
• 最右小于target的位置+1，即最右isBadVersion==false的位置+1，即最左插入位置，即最左边的一个isBadVersion==true；

代码

//s6
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;

        while(left <= right){
            int mid = left + (right - left) / 2;

            if(isBadVersion(mid)){
                right = mid - 1;
            } else {
                left = mid + 1;
            } 
        }

        return left;
    }
}

复杂度

time: O(logN) space: O(1)

[xuhzyy]

思路

二分查找法

代码

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while(left <= right):
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

复杂度分析

• 时间复杂度：O(log(n))
• 空间复杂度：O(1)

[CodingProgrammer]

思路

二分法

代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left + 1 < right) {
            int mid = left + ((right - left) >> 1);
            boolean isBad = isBadVersion(mid);
            if (!isBad) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return isBadVersion(left) ? left : right;
    }
}

复杂度

• Time :O(logN)
• Space: O(1)

[rzhao010]

Thoughts Binary Search

Code

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n == 1) return n;
        int left = 1, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (isBadVersion(left)) {
            return left;
        }

        if (isBadVersion(right)) {
            return right;
        }
        return -1;

    }
}

Complexity Time: O(logn) Space: O(1)

[LuoXingbiao]

思路

找第一个错误的版本，适合用二分法。中间指针m去找第一个错误的版本号。

代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int i = 0;
        int j = n - 1;

        while(i <= j){
            int m = i + (j - i) / 2;
            if(!isBadVersion(m)){
                i = m + 1;
            }
            else{
                j = m - 1;
            }
        }
        return i;

    }
}

复杂度

时间复杂度：O(logN)

空间复杂度：O(1)

[shamworld]

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let l=0,r=n,res=0;
        while(l<=r){
            let mid = Math.floor(l+(r-l)/2);
            if(isBadVersion(mid)){
                res = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return res;
    };
};

[iambigchen]

思路

二分法求最左侧符合要求的值

这题如果mid用 (l+r)>>1 计算会超时

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * 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) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let l = 1
        let r = n
        while(l <= r) {
            let mid = Math.floor((l + r) / 2);
            if (isBadVersion(mid)) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return l
    };
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(logN)$
• 空间复杂度：$O(1)$

[linyang4]

思路

二分法, 先找到中间的版本, 如果中间的版本是badversion, 那么最早的basversion肯定是中间版本或者中间版本前面的版本, 如果不是badversion, 那么badversion肯定在中间版本后面, 不断缩小区间, 找中间版本进行判断, 就能找到最早的badversion

代码

var solution = function(isBadVersion) {
    return function(n) {
        let left = 1
        while(left <= n) {
            const mid = (left + n) >>> 1
            if (isBadVersion(mid)) {
                n = mid - 1
                if (!isBadVersion(n)) { return mid }
            } else {
                left = mid + 1
                if (isBadVersion(left)) { return left }
            }
        }
    }
}

复杂度

• 时间复杂度: O(logn)
• 空间复杂度: O(1)

[ZJP1483469269]

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l , r = 0 , n
        while l < r:
            mid = (l + r) // 2
            if not isBadVersion(mid):
                l = mid + 1
            else:
                r = mid 
        return r

[Zhang6260]

JAVA版本

这题是最经典的二分法了，注意的是取中间的值得时候需要考验越界的问题。

public class Solution extends VersionControl {
   public int firstBadVersion(int n) {
       //找打第一个返回为 true的
       //使用二分法
       int left = 1, right = n;
       while(left<right){
           int mid = (right-left)/2+left;
           if(isBadVersion(mid)){
               right = mid;
           }else{
               left = mid + 1;
           }
       }
       return left;
   }
}

时间复杂度：O(logn)

空间复杂度：O(1）

[last-Battle]

代码

• 语言支持：C++

C++ Code:

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int start = 1, end = n;
        int mid = 0;

        while (start <= end) {
            mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return isBadVersion(end) ? end : start;
    }
};

复杂度分析

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

[naomiwufzz]

思路：二分

套用能力检测二分模板

代码

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        # 能力检测二分
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            if isBadVersion(mid) == True:
                right = mid - 1
            else:
                left = mid + 1
        return left

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[wenlong201807]

代码块

var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function (n) {
    let left = 1,
      right = n;
    while (left < right) {
      const mid = Math.floor((right - left) / 2 + left);
      if (isBadVersion(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[alongchong]

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r){
            int mid = l + (r - l) / 2;
            if(isBadVersion(mid)){
                r = mid ;
            }else {
                l = mid + 1;
            }
        }return l;
    }
}

[tangjy149]

思路

二分，寻找最左边的第一个，但isbadversion是检测是否为错误版本

代码

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1,right=n;
        while(left<=right){
            int mid=left+((right-left)>>1);
            if(isBadVersion(mid)==false){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        if(left>n || isBadVersion(left)==false) return -1;
        return left;
    }
};

[callmeerika]

思路

二分法

代码

var solution = function(isBadVersion) {
    return function(n) {
        let low = 1;
        let high = n;
        while (low < high) {
            let mid = low + ((high - low)/2>>1);
            if(isBadVersion(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    };
};

复杂度

时间复杂度：O(logn)
空间复杂度：O(1)

[haixiaolu]

思路

二分法

代码 / python

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n

        while left <= right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1

        return left 

复杂度分析

• 时间复杂度： O(log n)
• 空间复杂度：O(1)

[zwang2244]

思路

binary search since the versions should be [good, good,..., bad, bad, bad, ...]

代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int i = 1;
        int j = n;
        while(i < j){
            int med = i + (j - i)/2;
            if(isBadVersion(med)){
                j = med;
            }else{
                i = med + 1;
            }
        }
        return i;
    }
}

复杂度分析

• 时间复杂度：O(logN)，其中 N 为数组长度。
• 空间复杂度：O(1)