[Leetcode] 278. First Bad Version

Problem Statement

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

 

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 Example

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

 

정수 'n'이 지정되면 첫 번째 불량 버전인 'n' 이전의 정수 'i'를 찾아야 한다.

여기서 isBadVersion은 i-1에 대해 true와 false를 반환한다.

이는 기본적으로 Bibinary search다!

mid가 0과 n 사이의 잘못된 버전인지 확인할 때마다 시작 및 끝 값을 계속 업데이트한다.

종료 시 mid가 잘못된 버전인지 확인하고 mid+1을 반환하지 않으면 반환한다.

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 : O(n). Assume that isBadVersion(version) takes constant time to check if a version is bad. It takes at most n−1 checks, therefore the overall time complexity is O(n).

Space complexity : O(1)

 

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 isBadVersion(mid) ⇒ false.  

 

We know that all versions preceding and including mid are all good.  

So we set left = mid + 1 to indicate that the new search space is the interval [mid + 1, right] (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 isBadVersion(mid) ⇒ true.

This tells us that mid may or may not be the first bad version, but we can tell for sure that all versions after mid can be discarded. Therefore we set right = mid as the new search space of interval [left, mid] (inclusive).

In our case, we indicate left and right as the boundary of our search space (both inclusive).

This is why we initialize left = 1 and right = n.

 

How about the terminating condition? We could guess that left and right 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.

 

 

 

Complexity analysis

 

Time complexity : O(logn). The search space is halved each time, so the time complexity is O(logn)

Space complexity : O(1)