Leetcode: First Bad Version

문제설명

여러분은 프로덕 매니저(PM)이다. 여러분의 역할은 팀을 이끌어 새로운 제품을 개발해야 한다.
불행히도, 여러분의 최신 상품 퀄리티 체크에서 실패하고 말았다.
각각의 버전은 이전 버전에 기반을 두고 개발하였으므로 악성 버전 이후 모든 버전은 사용하지 못하는 버전이다.

여러분은 어떤 버전이 악성 버전인지 확인할 수 있도록 주어진 API는 isBadVersion(_ :Int)이다.

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

문제풀이

• 이진 탐색을 사용한다.

/**
 * The knows API is defined in the parent class VersionControl.
 *     func isBadVersion(_ version: Int) -> Bool{}
 */

class Solution : VersionControl {
   func firstBadVersion(_ n: Int) -> Int {
        return helper(1, n)
    }
    func helper(_ low: Int, _ high: Int) -> Int {
        let mid = (low+high)/2
        if low == high {
            return isBadVersion(mid) ? mid : mid-1
        }
        if isBadVersion(mid) {
            return helper(low, mid)
        } else {
            return helper(mid+1, high)
        }
    }

}