LeetCode [278]: First Bad Version

📌 LeetCode [278]: First Bad Version

---

문제 설명 📄

제품 버전이 1부터 n까지 순서대로 제공됩니다.
어떤 버전부터 "나쁜 버전"(bad version)이 시작됩니다.
isBadVersion(version: int) -> bool API를 사용하여 첫 번째 나쁜 버전을 찾아야 합니다.

---

문제 해결 접근 📋

1. 이진 탐색:
   • left와 right 포인터를 설정하여 탐색 범위를 줄입니다.
   • 중간 값 mid를 계산하고 isBadVersion(mid)로 확인합니다.
     • mid가 나쁜 버전이면 right = mid - 1로 갱신하여 더 작은 범위를 탐색.
     • 그렇지 않으면 left = mid + 1로 갱신하여 더 큰 범위를 탐색.
2. 결과 반환:
   • 탐색이 끝난 후 첫 번째 나쁜 버전(left)을 반환합니다.

---

Solution 💻

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n

        while left <= right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1

        return left

시간 복잡도 ⏲️

• 시간 복잡도: O(log n)
  • 이진 탐색을 사용하여 탐색 범위를 절반으로 줄입니다.

공간 복잡도 🗄️

• 공간 복잡도: O(1)
  • 추가 공간을 사용하지 않고 포인터로 탐색.

---