First Bad Version

Patrick Leaton
Published: March 15, 2021, 9:03 p.m.
Problem Description

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

  • 1 <= bad <= n <= 2^31 - 1

 

The description was taken from https://leetcode.com/problems/first-bad-version/.

Problem Solution

#O(log N) Time, O(1) Space
class Solution:
    def firstBadVersion(self, n):
        left, right = 1, n
        while left < right:
            mid = (left + right)//2
            if isBadVersion(mid) is True:
                right = mid
            else:
                left = mid + 1
        return left 

Problem Explanation

We are given an input that is in sorted order and we are looking for a specific value within that input.

When we see a requirement like this, a binary search is usually a good approach.

We initialize our left and right bounds of the search at the first and last versions.  Then, we will take the average between the pointers.  If the middle version is a bad version, then we will move our right pointer to the middle version so that we can continue to look for the first bad version.  If the middle version isn't bad, then we will move our left pointer past the middle version because we haven't gotten to the bad versions yet.  Once the pointers overlap, they will have overlapped on the first bad version.

 Let's initialize our left pointer to the first version and our right pointer to the last bad version.

        left, right = 1, n

 

While the pointers haven't overlapped, we will continue searching for the first bad version.

        while left < right:

 

During each iteration, we’ll initialize our middle pointer as the mean between the left and right pointers.

            mid = (left + right)//2

 

If the middle pointer is a bad version, we’ll move further down the left side of the array by setting our right pointer to the middle pointer. Remember, we want to know the earliest bad version.

            if isBadVersion(mid) is True:
                right = mid

 

If the middle version isn’t bad, then that means the first bad version came later than where we are currently so we’ll set our left pointer one version after the middle pointer.

            else:
                left = mid + 1

 

Once we break out of our loop it means that our left and right pointer have overlapped so we can return either pointer, let's choose the left one.

        return left