[003]First Bad Version

 

문제: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3316/

---

이분 탐색 문제입니다. mid를 구한 후 Bad Version이 나왔다면, 상한을 en = mid 으로 줄여서

탐색범위를 절반씩 줄여나가면 됩니다. 시간복잡도 O(logN)

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

class Solution {
public:
    int firstBadVersion(int n) {
        long long int st, en,mid, before;
        st = 0;
        en = (long long int)n+1;
        
        while (st < en) {
            mid = (st+en)/2;
            
            bool ret = isBadVersion(mid);
            if (ret) {
                en = mid;
                before = en;
            } else {
                st = mid + 1;
            }
        }
        return (int)before;
    }
};