[Kotlin] Leetcode 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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

 

Example 1:

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.

Example 2:

Input: n = 1, bad = 1
Output: 1

 

Constraints:

• 1 <= bad <= n <= 231 - 1

---

Summary

이 문제는 매우 간단한 문제이지만 생각을 깊게 하지 않으면 미묘한 함정에 빠질 수 있습니다.

그 외에는 아주 유명한 알고리즘을 적용해서 풀면 됩니다.

Solution

---

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

가장 쉬운 방법은 선형 스캔을 수행하여 무작정 찾아보는 방법입니다.

/* The isBadVersion API is defined in the parent class VersionControl.
      def isBadVersion(version: Int): Boolean = {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        for(i in 0..n)
        {
            if(isBadVersion(i)) return i
        }
        return n
	}
}

 

Complexity analysis

• Time complexity : O(n). isBadVersion(version)에서 버전이 나쁜지 확인하는데 일정한 시간이 걸린다고 가정할 때 최대 n-1개의 검사가 필요하므로 전체 시간 복잡도는 O(n)입니다. 
• Space complexity : O(1).

 

---

Approach #2 (Binary Search) [Accepted]

이 문제를 쉽게 해결하기 위해 Binary Search를 사용한다는 것을 생각해내는 것은 그렇게 어렵지는 않았습니다.

아래에서 매번 검색 공간을 절반으로 줄이는 방법을 살펴보겠습니다.

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

isBadVersion(mid)⇒false인 위의 첫번째 시나리오를 살펴보겠습니다

mid를 포함하여 mid 이전의 모든 version이 Good이라는 것을 알고 있습니다.

그래서 우리는 새로운 검색 공간 [mid + 1, right]을 탐색하기 위해 left = mid + 1을 설정했습니다.

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

 

남은 시나리오는 isBadVersion(mid)⇒true 뿐입니다. 이것은 mid가 첫 번째로 Bad가 되는 버전일 수도 있고 아닐 수도 있다는 것을 말하지만 mid 이후의 모든 버전은 Bad임을 확실히 알 수 있습니다.

따라서 right = mid를 설정하여 [left, mid]로 새로운 검색 공간을 설정합니다.

 

이 경우 검색 공간의 경계로 left와 right를 나타냅니다. (둘 다 포함)

이것이 우리가 left = 1 및 right = n을 초기화 하는 이유입니다.

 

종료 조건은 어떤가요? 

우리는 left와 right가 결국 만나서 그것이 첫 번째 잘못된 버전임에 틀림없다고 추측할 수 있지만, 어떻게 확신할 수 있을까요?

 

공식적인 방법은 귀납법으로 증명하는 것인데, 관심이 있다면 스스로 아래 사이트를 읽어보세요

http://www.cs.cornell.edu/courses/cs211/2006sp/Lectures/L06-Induction/binary_search.html

Showing Binary Search correct using induction

다음은 인터뷰 중에 이진 검색 알고리즘의 정확성을 신속하게 증명하는 유용한 팁입니다.

크기 2의 입력을 테스트하기만 하면 됩니다.

 

위의 두 시나리오(GB/BG case) 모두에 대해 검색 공간을 단일 요소(답이어야 함)로 줄이는지 확인하십시오.

그렇지 않으면 알고리즘이 종료되지 않습니다.

 

mid = (left + right) / 2 로 설정할 경우 매우 주의해야 합니다.

Python과 같이 overflow가 발생하지 않는 언어를 사용하지 않는 한 left + right는 overflow가 발생할 수 있습니다.

이 문제를 해결하는 한 가지 방법은 left + right 대신 left + (right - left) / 2를 사용하는 것입니다.

 

이 미묘한 overflow 버그에 빠진 사람은 혼자가 아닙니다.

Joh Bentley가 자체적으로 구현한 Binary Search에도 이 overflow 버그가 있었고 20년 넘게 감지되지 않은 채고 있었습니다. https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

 

/* The isBadVersion API is defined in the parent class VersionControl.
      def isBadVersion(version: Int): Boolean = {} */

class Solution: VersionControl() {
    override fun firstBadVersion(n: Int) : Int {
        var startN = 0
        var endN = n
        while(startN < endN)
        {
            val midN = startN + (endN - startN) /2
            if (isBadVersion(midN))
            {
                endN = midN
            } else
            {
                startN = midN + 1
            }
        }
        return startN
	}
}

Complexity analysis

• 시간 복잡도 : O(logn). 검색 공간은 매번 절반으로 줄어들어듬, 시간 복잡도는 O(logn).
• 공간 복잡도 :O(1).