First Bad Version

Intuition

Approach

search divide and check mid
search until left valid

이분탐색을 통해 중앙값이 문제가 있으면 end 를 변경하고
문제가 없으면 다시 first 가 문제가 있는지 검사하는것을 반복

Complexity

• Time complexity:

log(N)

• Space complexity:

O(1)

Code

C++

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

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

            }
        }

        return end;
    }
};