Introduction

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.

1
2
3
4
5
6
7

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.

1
2
3

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Process

Using a binary search done in Leetcode Binary Search 704, I was able to get the first bad version.

First, I initialised my left variable to 1 as the lower limit was 1 and I couldn’t start from 0. I initialised right to be n for the number of versions.

In the same while loop, I calculated the mid index again, but this time with right shift. I first checked with the isBadVersion API for the midpoint. If it is true, I’ll set the firstIndex variable to the midpoint, and the right index to mid - 1 to check the left side.

If the first condition is not met, I’ll check the next half by updating mid + 1 in the while loop.

At the end of the loop, firstIndex is returned as the First Bad Version.

This solution takes a Time Complexity of $O(\log n)$ and Space Complexity of $O(1)$

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        firstIndex = -1

        while left <= right:
            mid = (left + right) >> 1
            if isBadVersion(mid):
                firstIndex = mid
                right = mid - 1
            else:
                left = mid + 1
        return firstIndex

Afterthoughts

This is almost a duplicate of Leetcode Binary Search 704, where binary search is used as the most efficient algorithm, splitting the sorted array into half each time through the iteration to search for the values required. I need more practice to be familiar and comfortable with these searching algorithms.