current position:Home>C language algorithm problem: the first wrong version

C language algorithm problem: the first wrong version

2022-01-27 02:37:44 WE-ubytt

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

copyright notice
author[WE-ubytt],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270237421049.html

Random recommended