Python의 첫 번째 잘못된 버전

회사에서 한 제품 관리자가 신제품을 개발하는 팀을 이끌고 있다고 가정합니다. 최신 버전이 품질 검사에 실패했다고 가정합니다. 각 버전은 이전 버전을 기반으로 개발되었기 때문에 나쁜 버전 이후의 모든 버전은 나쁜 버전이 됩니다. 따라서 n개의 요소 [1, 2, … n]를 가진 배열 A가 있고 이 배열에서 첫 번째 잘못된 버전을 찾아야 합니다.

isBadVersion(version_id) 함수가 있다고 가정하면 버전이 나쁜지 여부를 반환합니다. 예를 들어, n =5이고 버전 =4가 첫 번째 잘못된 버전이라고 가정합니다. 따라서 isBadVersion(3)이 false를 반환하면 isBadVersion(5)이 true를 반환하고 isBadVersion(4)도 true를 반환하면 첫 번째 잘못된 버전은 4입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n <2이면 n을 반환합니다.
• 이진 검색 방식을 수행하여 주어진 함수를 사용하여 잘못된 버전을 감지합니다.

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

first_bad = 0
def isBadVersion(version):
   if version >= first_bad:
      return True
   return False
class Solution:
   def firstBadVersion(self, n):
      if n <2:
         return n
      start = 1
      end = n
      while(start<=end):
         mid = (start+end)//2
         if isBadVersion(mid) and not isBadVersion(mid-1):
            return mid
         elif isBadVersion(mid-1):
            end = mid-1
         else:
            start = mid+1
ob1 = Solution()
first_bad = 4
op = ob1.firstBadVersion(5)
print(op)

입력

5
4

출력

4