[leetCode] 278. First Bad Version 풀이

278. First Bad Version
isBadVersion() API 함수가 주어짐 -> 오류가 있는 버전이면 True 반환
에러가 발생한 이후의 버전은 모두 에러 발생, 처음 에러가 발생한 버전을 찾아라

 

입력 값의 크기 : 1 <= bad <= n <= 2^31 - 1 이므로,

선형 탐색으로 for문을 통해 1 부터 n 까지 처음 에러 발생한 버전을 check 하면 시간초과 발생할 것 같다. : O(n) 의 복잡도

-> 이진 탐색하는 것이 탐색 시간을 줄일 수 있을 것

 

결과

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 이진 탐색 수행
        left = 1
        right = n
        bad = -1
        while left <= right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                # 이전 버전 체크
                right = mid - 1
                bad = mid
            else:
                left = mid + 1
        return bad

이진 탐색을 통해 범위를 줄여 나갔다~~~~~

 

결과

Visual Code 테스트용 코드

# leetCode 278.First Bad Version
class Solution(object):
    def __init__(self,bad):
        self.bad = bad

    def isBadVersion(self, version):  # 임의로 내가 구현
        if version >= self.bad:
            return True
        else:
            return False

    def firstBadVersion(self, n):
        # 이진 탐색 수행
        left = 1
        right = n
        bad = -1
        while left <= right:
            mid = (left + right) // 2
            if self.isBadVersion(mid):
                    # 이전 버전 체크
                right = mid - 1
                bad = mid
            else:
                left = mid + 1
        return bad

# 인스턴스 생성 시, 인자값을 첫번째 bad version 으로 설정
test1 = Solution(4)
test2 = Solution(1)
test3 = Solution(3)

print(test1.firstBadVersion(5)) # 4
print(test2.firstBadVersion(1)) # 1
print(test3.firstBadVersion(7)) # 3