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

java中的代码

    public static int firstBadVersion(int n) {
        int low = 0;
        int high = n;
        while (low < high) {
            int mid = low / 2 + (high - low) / 2; // 直接调用(high + low) / 2求均值会存在越界的问题
            if (isBadVersion(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
 

python1的代码

# The isBadVersion API is already defined for you.

# def isBadVersion(version: int) -> bool:

class Solution:

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

        low,high = 0,n

        while(low < high):

            mid = low /2 + (high - low )/2

            if(isBadVersion(mid)):

                high = mid 

            else:

                low = mid + 1

        return low

超出时间限制

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

python代码
# 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
        """
        a = 0
        i = n//2
        # 临界点是a和n版本相邻，且右版本大于左版本
        while not(n-a == 1): 
            if isBadVersion(i):
                # n是右值
                n = i 
            else:
                # a是左值
                a = i 
            # i是中值
            i = (a + n) // 2
        # 最后一个i=（a+n）//2=a,此时a是最后一个flase，n是第一个true
        #所以我们需要返回n，n=a+1=i+1
        return i + 1

作者：i3rave-rubin74b
链接：https://leetcode.cn/problems/first-bad-version/solution/by-i3rave-rubin74b-8w2c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

# The isBadVersion API is already defined for you.

# def isBadVersion(version: int) -> bool:

class Solution:

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

        a = 0

        i = n//2

        #临界点时a和n版本相邻，且由版本大于左版本

        while not(n-a == 1):

            if isBadVersion(i):

                #n是右值

                n = i

            else:

                #a是左值

                a = i

            #i是中值

            i = (a + n) // 2

        #最后一个i =(a + n)//2 = a,此时a是最后一个flase,n是第一个true，所以我们需要返回n , n = a + 1 = i + 1

        return i + 1