278. First Bad Version - cocoder39/coco39_LC GitHub Wiki

278. First Bad Version

int firstBadVersion(int n) {
        int start = 1, end = n; //[start, end]
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            }
            else{
                start = mid;
            }
        }
        
        if (isBadVersion(start)) {
            return start;
        }
        return end;
    }

what if total number n is unknown

int firstBadVersion(int n) {
        int start = 1, end = 1;
        for (; end <= n && ! isBadVersion(end) && end <= INT_MAX / 2; end *= 2) ;
        if (end > n) {
            start = end / 2;
            end = n;
        } else if (! isBadVersion(end)) {
            start = end;
            end = n;
        } else { //isBadVersion(end)
            start = end / 2;
        }
        
        while (start + 1 < end) { //end - start >= 2
            int mid = start + (end - start) / 2; //mid > start+1 && mid = (end + start)/2 < end 
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (isBadVersion(start)) {
            return start;
        } else {
            return end;
        }
    }