278. First Bad Version


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.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.


Summary

This is a very simple problem. There is a subtle trap that you may fall into if you are not careful. Other than that, it is a direct application of a very famous algorithm.

Solution

Approach #1 (Linear Scan) [Time Limit Exceeded]

The straight forward way is to brute force it by doing a linear scan.

Complexity analysis

  • Time complexity : . Assume that takes constant time to check if a version is bad. It takes at most checks, therefore the overall time complexity is .

  • Space complexity : .

Approach #2 (Binary Search) [Accepted]

It is not difficult to see that this could be solved using a classic algorithm - Binary search. Let us see how the search space could be halved each time below.

Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = Good, B = Bad
 |       |       |
left    mid    right

Let us look at the first scenario above where . We know that all versions preceding and including are all good. So we set to indicate that the new search space is the interval (inclusive).

Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = Good, B = Bad
 |       |       |
left    mid    right

The only scenario left is where . This tells us that may or may not be the first bad version, but we can tell for sure that all versions after can be discarded. Therefore we set as the new search space of interval (inclusive).

In our case, we indicate and as the boundary of our search space (both inclusive). This is why we initialize and . How about the terminating condition? We could guess that and eventually both meet and it must be the first bad version, but how could you tell for sure?

The formal way is to prove by induction, which you can read up yourself if you are interested. Here is a helpful tip to quickly prove the correctness of your binary search algorithm during an interview. We just need to test an input of size 2. Check if it reduces the search space to a single element (which must be the answer) for both of the scenarios above. If not, your algorithm will never terminate.

If you are setting , you have to be very careful. Unless you are using a language that does not overflow such as Python, could overflow. One way to fix this is to use instead.

If you fall into this subtle overflow bug, you are not alone. Even Jon Bentley's own implementation of binary search had this overflow bug and remained undetected for over twenty years.

Complexity analysis

  • Time complexity : . The search space is halved each time, so the time complexity is .

  • Space complexity : .

Submit Solution