(C++) - LeetCode (easy) 278. First Bad Version

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

First Bad Version - LeetCode

이분 탐색 문제였습니다.

📕 풀이방법

📔 풀이과정

처음으로 isBadVersion(x)값이 true가 나오는 x를 찾는 문제로 x가 1억을 넘을 수 있기 때문에 O(n) 시간복잡도로는 풀 수 없습니다. 따라서 O(logn)의 복잡도를 갖는 algorithm을 사용해야 합니다.

 

isBadVersion(x)이 0이 나온다면 l을 mid + 1로 만들어주면 최종적으로 while문을 나온 l값은 isBadVersion(l)이 1이 되므로 정답이 됩니다. 이를 반환해줍니다.

 

* (l + r) / 2에서 (l + r) 이 int범위를 초과할 수 있으므로 자료형을 고려해 l + (r - l) / 2로 공식을 고쳐 사용해야 합니다.

---

📕 Code

📔 C++

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(isBadVersion(mid)) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.