Identify bad versions program

Question

I am doing this problem:

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.

I have this code:

class Solution:
    def firstBadVersion(self, n):
        for ver in range(n+1):
            if isBadVersion(ver):
                return ver

This works but is too slow for large n's. How can I improve the performance of this operation?

_{For anyone who wanted to see the original problem, see here}

Answer 1

The problem is the famously known "guess the number game". If we change the terminology of isBadVersion to:

isBadVersion returns True if your guess is too high, and false if your number is too low.

Then the challenge becomes obvious. To solve the well known problem you can perform a binary search. You divide the possible numbers by into two groups by picking the middle number. Then you divide the divided group into two more groups, by picking the middle of the higher or lower group, etc. Until you get the number. You can then solve the challenge calling the function in \$O(\log(n))\$ time (calls) rather than \$O(n)\$.

Answer 2

As already pointed out, your solution takes O(n) guesses and binary search would only need O(log n) guesses. We can leverage Python's bisect module by feeding it a proxy to the isBadVersion function:

class Solution:
    def firstBadVersion(self, n):
        class Proxy:
            def __getitem__(_, i):
                return isBadVersion(i)
        return bisect_left(Proxy(), True, 1, n)

Also, the versions are numbered 1 to n, but you're checking 0 to n. Not a performance issue, but requesting information about an invalid version number could lead to an error being raised.