simple clean fast recursive binary search c++ solution


  • 0
    Y

    In general, binary search hold the form like "If this one satisfies the condition, the following ones also satisfy". And the task would always like "find the first one hold that condition". In other words, we could simply exchange the API function isBadVersion(int n)to some other function like someTestFunction(int somePointInTheArray) to solve other problems using binary search.

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution {
    public:
        int firstBadVersion(int n) {
            return binary(1, n);
        }
        int binary(int low, int high) {
            if(low == high) return isBadVersion(low)? low : 0;
            int mid = low + (high - low) / 2;
            if(isBadVersion(mid)) return binary(low, mid);
            return binary(mid + 1, high);
        }
    };
    

Log in to reply
 

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