【Day 38 】2022-05-08 - 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 是第一个错误的版本。

[xixiao51]

Idea

Binary Search

Code

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) == false) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }
}

Complexity Analysis

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

[houmk1212]

思路

二分查找，查找最左边满足条件的位置。

代码

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 - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

复杂度

• 时间复杂度：O（logN）
• 空间复杂度：O（1）

[Yongxi-Zhou]

思路

最后要返回left指针

代码

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

    class Solution:
        def firstBadVersion(self, n: int) -> int:
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) >> 1
                if isBadVersion(mid):
                    hi = mid - 1
                else:
                    lo = mid + 1
            return lo

复杂度

time O(logN) space O(1)

[gitbingsun]

题目地址(278. 第一个错误的版本)

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

题目描述

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

假设你有 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

提示：

1 <= bad <= n <= 231 - 1

前置知识

• 二分法

代码

• 语言支持：C++

C++ Code:

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

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        int m;
        int ret;
        while (l<=r) {
            m = l + (r-l)/2;
            if (isBadVersion(m)) { // m is wrong, but might not be the first wrong one
                r = m - 1;
                ret = m;
            } else {
                l = m + 1;
            }
        }

        return ret;
    }
};

复杂度分析

令 n 为数组长度。

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

[MoonLee001]

思路

二分

代码

var solution = function(n) {
  let left = 1, right = n;
  while(left <= right) {
    const mid = Math.floor((right - left) / 2) + left;
    if (isBadVersion(mid)) {
      right = mid - 1;
    } else if (!isBadVersion(mid)) {
      left = mid + 1;
    }
  }
  return left;
}

复杂度分析

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

[freedom0123]

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

[PFyyh]

题目地址(278. 第一个错误的版本)

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

题目描述

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

假设你有 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

 

提示：

1 <= bad <= n <= 231 - 1

前置知识

公司

• 暂无

思路

关键点

• 二分查找，找到最左第一个符合条件的元素

代码

• 语言支持：Java

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 left=1,right=n;
        return search(left,right);
    }
    int search(int left,int right){
        int mid = left+(right-left)/2;
        if(right-left<=1){
            return isBadVersion(left)?left:right;
        }
        if(isBadVersion(mid)){
            return search(left,mid);
        }else{
            return search(mid,right);
        }

    }
}

复杂度分析

令 n 为数组长度。

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

[okbug]

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) {
            let mid = left + ((right - left) >> 1);
            if (isBadVersion(mid)) right = mid - 1;
            else left = mid + 1;
        }

        return left;
    };
};

[wychmod]

思路

找到最右边的false ，然后下标+1就是第一个true了

代码

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

时间复杂度

时间复杂度Ologn 空间复杂度O1

[Joyce94]

# 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 + 1 < right:
            mid = (left + right) // 2 
            if isBadVersion(mid) is False:
                left = mid 
            else:
                right = mid 
        if isBadVersion(left) is True:
            return left 
        return right 

[zzz607]

思路

直接二分搜索

代码

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

复杂度分析

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

[xingchen77]

思路

二分法，左右往中间查询

代码

    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)

[ZacheryCao]

Idea

Binary Search

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
        """
        if n == 1:
            return n
        start, end = 1, n
        while start < end:
            mid = (start+end)//2
            if isBadVersion(mid):
                if mid -1==0 or not isBadVersion(mid - 1):
                    return mid
                else:
                    end = mid
            else:
                start = mid + 1
        return start

Complexity:

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

[KelvinG-LGTM]

思路

= Binary search find the leftmost item.

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: 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(logN)

空间复杂度

O(1)

[caterpillar-0]

思路

二分查找，注意right边界=mid，而不是mid+1

代码

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

复杂度分析

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

[ghost]

思路

二分查找

代码

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: 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（logN） 空间：O（1）

[tensorstart]

思路

二分法

代码

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){
            let mid=(left+right)>>>1;
            if(isBadVersion(mid)) right=mid-1;
            else left=mid+1;
        }
        return left;

    };
};

复杂度分析

时间O(logn) 空间O(1)

[Jessie725]

Idea

Binary search. if target is mid, let right = mid cause we need to find the left most target. thus we need to use while(left < right) instead of <=, which will generate inifinate loop

Code

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

Complesity

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

[testeducative]

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

[Venchyluo]

二分模版题。

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): #start from it or before it
                right = mid
            else:
                left = mid + 1

        return left

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

[MichaelXi3]

Idea

• 二分法

  Code

  public class Solution extends VersionControl {
  public int firstBadVersion(int n) {
      int left = 1, right = n, ans = -1;
      while (left <= right) {
          int mid = left + (right - left) / 2; // to avoid overflow incase (left+right)>2147483647
          if (isBadVersion(mid)) {
              ans = mid; // record mid as current answer
              right = mid - 1; // try to find smaller version in the left side
          } else {
              left = mid + 1; // try to find in the right side
          }
      }
      return ans;
  }
  }

[xil324]

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

time complexity; binary search o(logn)

[KWDFW]

Day38

278、第一个错误的版本

javascript #二分法

思路

1、左侧的是未出错的，右侧的是出错的，查找临界值

2、每次都查找中间的值

3、当中间的值出错时，就缩小右边界，不出错时，就缩小左边界

4、查到临界版本

代码

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){
          let mid=Math.floor((left+right)/2)
          if(isBadVersion(mid)){
            right=mid-1
            //查到出错版本就再往前找找
          }
          else{
            left=mid+1
            //查到未出错版本就再往后找找
          }
        }
        return left
    };
};

复杂度分析

时间复杂度：O(logn)

空间复杂度：O(1)

[oneline-wsq]

思路

二分法

代码

# 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=1
        right=n
        while left <=right: # 一开始写成！=条件，结果超时
            mid=(left+right)//2
            if isBadVersion(mid): # 结果为true
                right=mid-1
            else:
                left=mid+1
        return left

复杂度分析

时间复杂度：O(logN)

空间复杂度：O(1)

[1973719588]

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) == True:
                r = mid - 1
            if isBadVersion(mid) == False:
                l = mid + 1

        return l

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

[physicshi]

思路

二分法

代码

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

复杂度

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

[miss1]

思路

二分

代码

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

复杂度分析

time: O(logn)

space: O(1)

[Davont]

var solution = function(isBadVersion) {
    return function(n) {
        let left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            const mid = Math.floor(left + (right - left) / 2); // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    };
}

[zhulin1110]

题目地址(278. 第一个错误的版本)

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

题目描述

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

假设你有 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

 

提示：

1 <= bad <= n <= 231 - 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 left = 0;
        let right = n;
        while (left <= right) {
          let mid = Math.floor(left + (right - left) / 2);
          if (isBadVersion(mid)) {
            right = mid - 1;
          } else {
            left = mid + 1;
          }
        }
        return right + 1;
    };
};

复杂度分析

令 n 为版本数。

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

[XXjo]

思路

二分法

代码

var solution = function(isBadVersion) {
    return function(n) {
        let left = 1;
        let right = n;
        while(left <= right){
            let mid = Math.floor(left + (right - left) / 2);
            if(isBadVersion(mid)){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    };
};

复杂度分析

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

[liuguang520-lab]

思路

使用二分查找法

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

复杂度分析

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

[L-SUI]

/**
 * 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 i=1;
        while(i<n){
            let mid = Math.ceil((i+n)/2);
            if(isBadVersion(mid)) {
                n=mid-1;
                if(!isBadVersion(mid-1)) return mid;
            }else {
                i=mid+1;
            }
        }
        return n
    };
};

[ShawYuan97]

思路

二分法

关键点

• 二分法并记录min(ans)

代码

• 语言支持：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
        """
        l,r,ans = 1,n,n
        while l<=r:
            mid = (l+r)>>1
            if not isBadVersion(mid):
                l = mid + 1
            else:
                ans = min(ans,mid)
                r = mid - 1
        return ans 

复杂度分析

令 n 为数组长度。

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

[Magua-hub]

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

class Solution {
public:
    int firstBadVersion(int n) {
        long long  l = 0, r = n;
        while(l < r) {
            long  mid = l + r + 1 >> 1;
            if(!isBadVersion(mid)) l = mid;
            else r = mid - 1;
        } 
        return (int)r + 1;
    }
};

[JiangWenqi]

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long mid = (long)l + r >> 1;
            if (isBadVersion(mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

[JasonHe-WQ]

思路： 二分法 代码：

# 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 = 0
        right = n
        while left < right:
            mid = (left + right)//2
            if not isBadVersion(mid):
                left = mid + 1
            else:
                right = mid
        return left

[xiayuhui231]

题目

第一个错误的版本

思路

二分法查找

代码

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while(left < right){
            int mid = left + (right-left)/2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return right;

    }
};

复杂度

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

[ShirAdaOne]

思路

278. 第一个错误的版本 https://leetcode-cn.com/problems/first-bad-version/

代码

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

复杂度分析

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

[Ellie-Wu05]

思路一：二分查找

代码

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:

        left = 1
        right = n

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

            else:
                left = mid+1

        return left

复杂度分析

时间：O(logn) 空间: O(1)

思路二：暴力解法也是可以的，但是超时了

代码

        for i in range(n):
                if isBadVersion(i):
                        return i
        return n

复杂度分析

时间：O（n) 空间：O（1）

[LQyt2012]

思路

二分法

代码

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

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

复杂度分析

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

[weihaoxie]

思路

• 二分法

  代码

  
  # 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 = 1 r = n ans = 1 while l <= r: mid = (l+r)//2 isbad = isBadVersion(mid) if isbad: ans = mid r = mid - 1 else: l = mid + 1 return ans

### 复杂度
- 时间复杂度O(logn)
- 空间复杂度O(1)

[mo660]

思路

二分法

代码

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

[Geek-LX]

5.8

思路

• 二分法

代码

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)
• 空间复杂度：O(1)

[youxucoding]

5月8日

【day38】

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 是第一个错误的版本。

思路：

二分搜索，不断向左侧逼近，直到找出最左侧出现的true

代码实现：

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

            }else {
                left = mid + 1;
            }
        }
        if(left < 1) {
            return 1;
        }
        return left;
    }
}

复杂度分析:

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

[zenwangzy]

// 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) / 2;
            if ( isBadVersion(mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

[revisegoal]

二分

令left = 1，right = n，mid = (left + right) / 2，若mid是错误的，说明mid之后都是错误的，都不是第一个错误，所以right = mid往左边找第一个错误，若mid不是错误的，说明错误都在mid右边，所以left = mid + 1往右边找第一个错误

/* 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 left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

• time: O(logn)
• space: O(1)

[BiN214]

    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 使用循环而不是递归减少复杂度
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }

[rzhao010]

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

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;

    }
}

[yangyuhuan]

var solution = function(isBadVersion) { /**

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

[bzlff]

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left = 0
        right = n

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