C language algorithm problem: the first wrong version

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 .

Example 1：

Input ：n = 5, bad = 4
Output ：4
explain ： call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
therefore ,4 It's the first wrong version .

Example 2：

Input ：n = 1, bad = 1
Output ：1

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/first-bad-version
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：
This question is actually a variant of binary search , The principle is the same , But some small details need to be paid attention to .
When we set the midpoint , Out-of-service （left + right）/ 2 form , When left and right All are int type , The initial value of both values exceeds int Limit half the size , that left + right There will be an overflow , So we should use left + (right - left) / 2 To prevent overflow when finding the midpoint .

Complexity analysis ：

Time complexity ：O(\log n)O(logn), among nn Is the number of versions given .
Spatial complexity ：O(1)O(1). We just need a constant space to hold a few variables .

Code ：

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

int firstBadVersion(int n) {
    
    int left = 1;
    int right = n;
    //  Conditions at the end of the cycle ： The left and right endpoints are the same 
    while(left < right)
    {
    
        int mid = left + (right - left)/2;//  Prevent overflow during calculation 
        if(isBadVersion(mid))//  Midpoint error 
        {
    
            right = mid;//  In the interval [left,mid] in 
        }
        else//  The midpoint is not wrong 
        {
    
            left = mid + 1;//  In the interval [mid,right] in 
        }
    }
    //  After the end of the cycle ,left = right
    return left;
}