【Day 38 】2021-10-17 - 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 是第一个错误的版本。

[yanglr]

思路:

直接使用二分搜索模板

方法: 二分搜索

代码:

实现代码: C++

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 0;
        int right = n; // 在区间 [0, n]中搜索
        while (left < right)
        {
            int mid = left + (right - left) / 2;  // 防止溢出
            if (isBadVersion(mid) == true)
                right = mid;
            else left = mid + 1;
        }
        return left;        
    }
};

复杂度分析:

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

[pophy]

思路

• 直接套用2分模板

Java code

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n; // [left, right]
        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;
    }
}

时间&空间

• 时间 O(log(n))
• 空间 O(1)

[kkwu314]

思路

二分

代码

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

复杂度

时间：O(logN)

空间：O(1)

[BreezePython]

思路

1. 二分查找
2. 题目中虚拟构建了 isBadVersion 方法用于判断结果是True or False。

   代码

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

   复杂度

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

[littlemoon-zh]

day 38

278. First Bad Version

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (isBadVersion(mid)) 
                hi = mid;
            else 
                lo = mid + 1;
        }
        return lo;
    }
}

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

[chenming-cao]

解题思路

二分法，寻找最左边的满足条件的值。因为题目中说一定有满足条件的值出现，所有可以省去检查边界的部分。

代码

/* 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 l = 1, 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)

[fzzfgbw]

思路

二分

代码

func firstBadVersion(n int) int {
    l:=1
    r:=n
    for l<=r {
        m:=(r-l)/2+l
        if isBadVersion(m) {
            r = m-1
        }else{
            l = m+1
        }

    }
    return l
}

复杂度分析

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

[q815101630]

套模板

直接上模板，问的是 最左严格等于的下标位置

# 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-1
            else:
                l = mid+1
        return l

time: O(logn) Space: O(1)

[yachtcoder]

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

[cdd111]

解题思路

采用二分查找

代码

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

    };
};

[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)$

[BpointA]

思路

二分法

Python3代码

# 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-1

        while left<=right:
            mid=(left+right)//2

            if isBadVersion(mid)==True and isBadVersion(mid-1)==False:
                return mid
            elif isBadVersion(mid-1)==True:
                right=mid-1
            else:
                left=mid+1

        return n

复杂度

时间复杂度：O(logn)

空间复杂度：O(1)

[zhangzz2015]

思路

• 使用标准binary search。采用[left right]。最后退出 [right left] 。 right是pass。left为fail的版本，因此返回left。

class Solution { public: int firstBadVersion(int n) {

    int left =1; 
    int right = n; 
    //[left right]
    while(left<= right)
    {
        int middle = left + (right - left)/2; 

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

    // return [right left] ; 
    return left; 

}

};

[JiangyanLiNEU]

Binary Search

• if the leftmost one is false, then return leftmost
• check middle item: if middle one is bad, then we shrink the range into first half
• otherwise, check second half
• Runtime = O(logn), Space = O(1)
• 感谢91算法，转码选手成功找到实习！

  JavaScript Code

  var solution = function(isBadVersion) {
  var check = function(low, high){
      if (low == high){return low;}
      else{
          if (isBadVersion(low)){return low;}
          let middle = Math.floor((low+high)/2);
          if (isBadVersion(middle)){
              return check(low, middle);    
          }else{
              return check(middle+1, high);
          };
      };
  };
  return function(n) {
      let low = 1;
      if (isBadVersion(low)){return low;}
      let high = n;
      let middle = Math.floor((low+high)/2)
      if (isBadVersion(middle)){
          return check(low, middle)
      }else{
          return check(middle+1, high)
      };
  };      
  };

[mmboxmm]

思路

二分

代码

Algo4

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        int ret = -1;

        while (l <= r) {
            int m = (l + r) >>> 1;
            if (isBadVersion(m)) {
                ret = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return ret;
    }
}

复杂度

O(logn)

[muimi]

思路

二分查找

代码

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

复杂度

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

[ZacheryCao]

Idea:

Binary search. The mid element of current search range can be four conditions:

1. It's the last good version, which means the mid + 1 is the first bad version. We should return mid + 1. We will consider case at the boundary later.
2. It's the first bad version, which means the mid - 1 is the last good version. We should return mid.
3. It's a part of good versions, which means the first bad version is on its right side. We should update left side of our search range to mid + 1
4. It's a part of bad versions, which means the first bad version is on its left side. We should update right side of our search range to mid - 1

When left side of our search range is larger than our right side, the search should be ended, we should return left side. It also could be the first bad version is the first version or the last version, which are the corner cases. If it's the first version, then when the search ends, the right side will be 0 and left side will be 1, we should return left side. If it's the last version, which means the last second version is the good version, we will hit our second condition.

Code:

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

Complexity:

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

[thinkfurther]

思路

使用二分法

代码

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

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

        return left

复杂度

时间复杂度 ：O(log N)

空间复杂度：O(1)

[comst007]

278. 第一个错误版本

---

思路

二分

代码

• C++

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

---

复杂度分析

n一个正整数

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

[nonevsnull]

思路

• 拿到题的直觉解法
  • 二分的题，目标是将题目匹配到模板；
  • 没匹配，就没想清楚，做出来也没意义；下次还是错；
  • 题目的意思是，找到第一个bad，并非找到bad即可，所以如果将问题定义为找到bad，则不是一个精确匹配的题，而是一个找最左匹配的题；
  • 根据题目条件，可以匹配的模版是： 寻找最左符合条件的值；第一个bad
  • 当然，如果非要用精确匹配的最简单模版，也是可以的，那要把问题定义为找到第一个bad，这就是精确匹配了，但是第一得需要进一步在判断条件中定义清楚 找到一个指定的bad，它的左侧要么为空，要么为good

最好使用最做匹配，因为精确匹配需要注意的edge case更多。 AC

代码

//寻找最左符合条件的值
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 0, right = n;

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

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

        if(left > n || !isBadVersion(left)){
            return -1;
        }
        return left;
    }
}

//精确匹配
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) && (mid - 1 == 0 || !isBadVersion(mid - 1))){
                return mid;
            } else if(isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

复杂度

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

[zjsuper]

idea 二分法 time O(logN)

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

[falconruo]

思路:

二分查找, 直接套模板，一次AC:

复杂度分析:

时间复杂度: O(logn), 其中n是给定版本 空间复杂度: O(1)

代码(C++):

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

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;

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

        return l;
    }
};

[ginnydyy]

Problem

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

Notes

• Binary search
• find the first bad, so when exit the while loop, check start first

Solution

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

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

Complexity

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

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

复杂度分析

令 n 为数组长度。

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

[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

[florenzliu]

Explanation

• use binary search

Python

# 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
            elif not isBadVersion(mid):
                left = mid + 1
        return left

Complexity:

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

[siyuelee]

二分查找，模板为寻找最左符合条件的值。

class Solution(object):
    def firstBadVersion(self, n):
        l, r = 1, n
        while l <= r:
            mid = (l + r) // 2
            if isBadVersion(mid) == True:
                r = mid - 1
            if isBadVersion(mid) < True:
                l = mid + 1
        if l >= n + 1 or isBadVersion(l) != True: return -1
        return l

T: logn S: 1

[Laurence-try]

思路

Binary search

代码

使用语言：Python3

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

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

[yuxiangdev]

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

}

[chang-you]

/* 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 < end) {
            int mid = (end - start) / 2 + start;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        if (isBadVersion(start)) return start;
        else return end;
    }
}

[AgathaWang]

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 二分法
        # tc: O(logN)
        l,r = 0, n 
        while l<=r:
            mid = (l+r)//2
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

[yingliucreates]

link:

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

代码 Javascript

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

复杂度分析

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

[erik7777777]

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

binary search to find the left boundary time : O(logn) space : O(1)

[RonghuanYou]

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

---

Time: O(log N)

Space: O(1)

[itsjacob]

Intuition

• using the binary search template for left-bound search

Implementation

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

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

Complexity

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

[qyw-wqy]

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;
            boolean isBad = isBadVersion(mid);
            if (isBad) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

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

[chakochako]

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

[joeytor]

思路

搜索范围是 [1,n], 所以 左右边界分别为 1, n

当 l≤r 时

​ 如果 isBadVersion(mid) 是 True 说明第一个出错的有可能在 mid 左边, 所以 r = mid-1

​ 如果 isBadVersion(mid) 是 False 说明第一个出错的有可能在 mid 右边, 所以 l = mid+1

最后返回 l, 因为 l 是在第一个出错的版本上, r 在最后一个没错的版本上

# 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) >> 1
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

复杂度

时间复杂度: O(logn) 二分查找的时间复杂度

空间复杂度: O(1)

[lilyzhaoyilu]

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

[tongxw]

思路

最左二分 如果是错误版本，那么右边界设定为这个版本，再去找左边还有没有更新的错误版本了。 如果不是错误版本，那么错误版本再右半区间。

代码

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

TC: O(logn) SC: O(1)

[akxuan]

二分查找

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

[carsonlin9996]

思路

-双指针， 每次折中 -找到left 和 right 两个指针， 先判断right是否是错误版本, 不然就是left

语言

java

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {

        int left = 0;
        int right = n;

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

            if (isBadVersion(mid) == true) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (isBadVersion(right) == true) {
            return right;
        }
        return left;   
    }
}

[Menglin-l]

思路：

使用二分法，因为第一个坏的之前全是好的，之后全是坏的，用isBadVersion()比较一下就行了.

---

代码部分：

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

        return left;
    }
}

---

复杂度：

Time: O(logN)

Space: O(1)

[pan-qin]

idea

two pointer

complexity

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

code:

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

[Moin-Jer]

思路

---

二分查看最左满足条件的值

代码

---

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

复杂度分析

---

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

[freedom0123]

/* 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 l = 1;
        int r = n;
        while(l<r){
            long tem  =(long) l+r>>1;
            int mid = (int)tem;
            if(isBadVersion(mid)){
               r = mid; 
            }else{
                l = mid+1;
            }
        }
        return l;       
    }
}

[zszs97]

开始刷题

题目简介

【Day 38 】2021-10-17 - 278. 第一个错误的版本

题目思路

• 二分法

题目代码

代码块

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; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
};

复杂度

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

[xbhog]

278. 第一个错误的版本

思路：

采用整数二分模板，需要注意的是mid取值溢出的风险

Java代码段：

/* 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 l = 1, r = n;
        while(l < r){
            //int mid = l+r>>1  可能会有溢出的风险
            int mid = l+(r-l)/2;
            if(isBadVersion(mid)) r = mid;
            else l = mid+1;
        }
        return l;
    }
}

复杂度分析：

时间复杂度：O(LogN)

空间复杂度：O(1)

[carterrr]

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

public class 第一个错误的版本_278{ // 找到 最小的true true时 r= mid false时 l = mid + 1 用 l ~ mid mid + 1 ~ r l = r时mid处刚好为true
public int firstBadVersion(int n) { int l = 1, r = n; while(l < r) { // int mid = (l+r) >> 1; int mid = l + (r - l)/2; // 防止计算时溢出 l + r 刚好大于整数最大值的时候会有问题

        if(!isBadVersion(mid)) { // 遇到错误版本  l = mid + 1 
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;

}

// 题目自己实现 
boolean isBadVersion(int version){return  false; }

}

[Daniel-Zheng]

思路

二分查找。

代码(C++)

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

复杂度分析

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