# Solution For First Bad Version

Problem Statement:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n` versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution:

The problem statement is essentially asking us to perform a binary search on a sorted list of `n` elements. We know that all versions after a bad version are also bad. Therefore, if version `mid` is bad, we know that the first bad version must be in the range [1, mid]. Similarly, if version `mid` is not bad, we know that the first bad version must be in the range [mid + 1, n]. We can use this observation to perform a binary search.

Let’s start by initializing the left and right pointers to the first and last versions, respectively. We’ll use a while loop to keep dividing the range in half until we find the first bad version.

`class Solution: def firstBadVersion(self, n): left = 1 right = n while left < right: mid = left + (right - left) // 2 if isBadVersion(mid): right = mid else: left = mid + 1 return left`

Initially, the range is [1, n]. We calculate the midpoint `mid` as shown above.

If `mid` is bad, we know that the first bad version must be in the range [1, mid], so we set `right = mid`. Otherwise, we know that the first bad version must be in the range [mid + 1, n], so we set `left = mid + 1`.

We repeat this process until the range is reduced to a single version. At this point, we have found the first bad version.

Note that we use the expression `left + (right - left) // 2` to calculate the midpoint. This is done to prevent integer overflow. If we use the expression `(left + right) // 2` and `left + right` is too large, we may get an incorrect result.

## Step by Step Implementation For First Bad Version

```/**
* public class SVNRepo {
*     public static boolean isBadVersion(int k);
* }
* you can use SVNRepo.isBadVersion(k) to judge whether
* the kth code version is bad or not.
*/

public class Solution {
/**
* @param n: An integer
* @return: An integer which is the first bad version.
*/
int start = 1, end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
end = mid;
} else {
start = mid;
}
}
return start;
}
return end;
}
}```
```# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool

class Solution:
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
left = 1
right = n
while left < right:
mid = left + (right - left) // 2
left = mid + 1
else:
right = mid
return left```
```/**
*
* @param {integer} version number
* @return {boolean} whether the version is bad
*     ...
* };
*/

/**
* @return {function}
*/
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {

let left = 1;
let right = n;

while(left < right){
let mid = Math.floor(left + (right - left)/2);
right = mid;
}
else{
left = mid + 1;
}
}

return left;
};
};```
```You can use the following pseudo-code to solve the problem:

/*
Returns true if the version passed in is a bad version, false otherwise.
*/

/*
*/

// Set left and right pointers.
left = 1
right = n

// Loop until left and right meet.
while left <= right:

// Get the middle version.
mid = left + (right - left) // 2

// Check if the middle version is a bad version.

// If it is, the first bad version is somewhere to the left
// of the middle version.
right = mid - 1

else:

// If it's not, the first bad version is somewhere to the right
// of the middle version.
left = mid + 1

// At this point, left > right, so the first bad version is the
// version pointed to by the left pointer.
return left```
```public class Solution {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]