Leetcode - 278. First Bad Version

문제

1 ~ n까지 값중에 isBadVersion(i) 함수를 호출해서 처음으로 bad값이 나오는 인덱스를 리턴하기.

Input: n = 5, bad = 4
Output: 4

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

/**
1. Constraints
 - n will be huge <= 2^32 -1
 - 1 <= n
 - check version from 1 (not 0)
 - 00011111 after bad all are bad
 - bad always less than n
 - isBadVersion() input range? from 0? or 1?
  
2. Ideas
 - linear search -> O(N)
   API will be called maximum 2^31 times
 - binary search -> O(logN)
   API will be called maximum 31*2 times
   need to find a spot (n[i-1] -> false/ n[i] -> true)
 - O(1) ?
 
3. Test Cases
 - extream input n = 1, bad == n, bad = 0
 - check n.lenth is even and odd
 
4. Coding
*/

해결 - linear search -> O(N)

int firstBadVersion(int n) {
    for (int i = 1; i <= n; i++)
        if (isBadVersion(i))
            return i;
    return 0;
}

해결 - binary search -> O(logN)

left와 right가 같아질때까지 루프를 반복. while (left < right)그리고 right = mid; 이부분 다시한번 살펴보기

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

int firstBadVersion(int n) {
    int left = 1, right = n, mid = 0;
    while (left < right) { // until same
        mid = left + ((right - left) >> 1);
        if (isBadVersion(mid)) { // bad
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    printf("(%d,%d)", left, right);
    return left;
}

코드를 더 빠르게 하기위해 int mid를 while밖으로 빼고, /2연산을 >> 1로 바꾸니 100%가 나왔다.
아래는 처음 구현했던 내용. isBadVersion() 를 두번씩 호출해야해서 더 비효율적인 코드.

int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) { // bad
            if (isBadVersion(mid - 1) == false)
                return mid;
            right = mid - 1;
        } else {
            if (isBadVersion(mid + 1) == true)
                return mid + 1;
            left = mid + 1;
        }
    }
    return left;
}