C Solution Using Binary Search - 0 ms


  • 0
    _

    Classic binary search algorithm.

    Providing a plain old C implementation because I didn't see one in a quick scan.

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    int firstBadVersion(int n) {
        int U = n;  // upper bound
        int L = 0;  // lower bound
        
        while (L <= U) {
            int M = L + (U -L) / 2;
            
            // if middle is a bad version, we need to check left half to find the __first__ instance
            if (isBadVersion(M)) {
                U = M - 1;
            // otherwise, we need to check right half --> bad version hasn't happened yet
            } else {
                L = M + 1;
            }
        }
        
        // when we come out of while loop, we have the first bad version, anchored at Lower Bound
        return L;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.