一.解法

https://leetcode-cn.com/problems/first-bad-version/
要點(diǎn)：二分法
Python，C++，Java都用了二分法。
本題是找兩堆版本的分界處，每次找中間位置然后調(diào)整left和right位置，最好畫圖判斷邊界是左邊還是右邊。

二.Python實(shí)現(xiàn)

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

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

三.C++實(shí)現(xiàn)

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

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

四.java實(shí)現(xiàn)

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