# 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
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）

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.

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
{

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