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
[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.
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
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.
The straight forward way is to brute force it by doing a linear scan.
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 : .
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.
Time complexity : . The search space is halved each time, so the time complexity is .
Space complexity : .