[leetcode] 278. First Bad Version

문제

 

 

풀이

bool isBadVersion(version) 함수가 주어지고 Bad가 처음 발생한 버전을 찾는 문제이다.

이진 탐색을 이용해서 풀면 되는 문제다.

 

Kotlin으로 풀었는데 한 가지 주의할 점은 middle를 구할 때 (high + low)/2 이용하면 Integer 범위를 초과할 수 있어 Time Limit Exceeded 이 나온다.

대신에 low + (high - low)/2 를 이용하면 해결할 수 있다.

• (low + high)/2 = low + (high-low)/2

 

 

코드

/* 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 start = 1
        var last = n

        while(start < last){
            val middle = start + (last - start) /2

            if(isBadVersion(middle)){
                last = middle
            } else {
                start = middle + 1
            }
        }

        return start

    }
}

---

참고

• https://leetcode.com/problems/first-bad-version/