[leetcode] 278. First Bad Version - Python

🔍 Problem

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

---

📰 문제풀이

• 제한 시간: 20분
• 성공 여부: 실패
• 실패 원인: 솔루션인 첫번째 bad 버전을 찾는데 완전탐색으로 접근했다.

---

📃 Solving Process

1. 이진 탐색으로 현재 내가 방문한 버전(middle)이 bad라면, 그 이전에 bad 버전 역시 존재하기 때문에 범위를 end = middle - 1 해준다.
2. 그게 아니라면(bad가 아니라면), 그다음에 오는 bad가 있는지 확인한다.
3. 이러한 방법을 통해 접근하면 end는 첫 번째 bad 전에 good을 가리키고, start는 첫 번째 bad를 가리키게 된다.

---

💻 Code

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start = 1
        end = n
        while start <= end:
            middle = (start + end) // 2
            if isBadVersion(middle):
                end = middle - 1
            else:
                start = middle + 1
        return start

---

⏱ Time Complexity

• 지난 이진 탐색 문제와 같이 시간 복잡도는 $O(\log_{}{N})$이 된다.

---

💾 Space Complexity

• 이진 탐색 과정에서 추가적인 메모리를 요구하지 않으므로 $O(1)$이다.