[LeetCode/C++]FirstBadVersion _ binary search

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

풀다가 어딘가 꼬여버린 알고리즘...

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

class Solution {
public:
    int firstBadVersion(int n) {
        bool nums[n+1];
        nums[0] = 0;
        for(int i=1;i<=n;i++){
            nums[i] = i;
        }
        int l = 1;
        int mid = n/2;
        int r = n;
        int first = 0;
        while(l<=r){
            nums[mid] = isBadVersion(mid); 
            if(!nums[mid]){
                nums[r] = isBadVersion(r);
                if(nums[r]){
                    l=mid+1;
                    mid = (l+r)/2;
                } else{
                    r = mid-1;
                    mid = (l+r)/2;
                }
            } else{
                if(!nums[mid-1]){
                    first = mid;
                    break;
                }else{
                    r = mid-1;
                    mid = (l+r)/2;
                }
            }
        }
        return first;
    }
};

 

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

class Solution {
public:
    int firstBadVersion(int n) {
        long long int beg, last, mid;
        beg = 1, last = n;
        long int pos =1;
        while(beg<=last){
            //mid 를 이렇게 계산하지 않으면 overflow 될수도
            mid = beg+(last-beg)/2;
            bool x = isBadVersion(mid);
            if(x==true){
                pos = mid;
                last = mid-1;
            }else
                beg = mid+1;
        }
        return pos;
    }
};

mid가 BadVersion이면, 일단 pos를 mid로 & last를 mid-1로(최초 오류버전을 탐색해야 하므로)

아니라면 beg는 mid+1을 탐색.

 

교훈 : 문제 포인트를 잘 읽자..!!!!

수도코드 작성하는 연습 하기🐣

 

참고 : https://www.studytonight.com/post/leetcode-solution-first-bad-version-problem