Leetcode skimming ---278

subject ： You are the product manager , Currently leading a team to develop new products . Unfortunately , The latest version of your product doesn't pass the quality test . Because each version is based on the previous version , So all versions after the wrong version are wrong .

Suppose you have n A version [1, 2, ..., n], You want to find out the first wrong version that caused all subsequent versions to go wrong .

You can call  bool isBadVersion(version)  Interface to determine version number version If there is an error in unit test . Implement a function to find the first wrong version . You should try to minimize calls to API The number of times .

Input ：n = 5, bad = 4

Output ：4

Method 1 ： Two points search

// 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) {  //  Cycle until the left and right end points of the interval are the same 
            int mid = left + (right - left) / 2;    //  Prevent calculation overflow 
            if (isBadVersion(mid)) {
                right = mid;    //  The answer in [left, mid] in 
            } else {
                left = mid + 1; //  The answer in [mid, right] in 
            }
        }  
        //  At this time there is left == right,  The interval is reduced to a point , Is the answer 
        return left;
    }
};

Complexity analysis

Time complexity ：O(logn)

Spatial complexity ：O(1)