# 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. */ public int findFirstBadVersion(int n) { // write your code here int start = 1, end = n; while (start + 1 < end) { int mid = start + (end - start) / 2; if (SVNRepo.isBadVersion(mid)) { end = mid; } else { start = mid; } } if (SVNRepo.isBadVersion(start)) { return start; } return end; } }

# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version): class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ if n == 1: return 1 left = 1 right = n while left < right: mid = left + (right - left) // 2 if isBadVersion(mid) == False: left = mid + 1 else: right = mid return left

/** * Definition for isBadVersion() * * @param {integer} version number * @return {boolean} whether the version is bad * isBadVersion = function(version) { * ... * }; */ /** * @param {function} isBadVersion() * @return {function} */ var solution = function(isBadVersion) { /** * @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); if(isBadVersion(mid)){ right = mid; } else{ left = mid + 1; } } return left; }; };

You can use the following pseudo-code to solve the problem: function isBadVersion(version): /* Returns true if the version passed in is a bad version, false otherwise. */ function firstBadVersion(n): /* Returns the first bad version. */ // 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 isBadVersion(mid): // 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 { public int FirstBadVersion(int n) { int left = 1; int right = n; while (left < right) { int mid = left + (right - left) / 2; if (IsBadVersion(mid)) { right = mid; } else { left = mid + 1; } } return left; } }