Bisection search -- O(log(n)) complexity -- C++


  • 0
    T
    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution {
    private:
        int firstBadVersionHelper(int start, int end)
        {
            if(start == end)
                return start;
            if(end == start + 1)
            {
                if(isBadVersion(start+1))
                    return start;
                else
                    return end;
            }
            int middle = (end-start)/2 + start;
            if(isBadVersion(middle+1) && !isBadVersion(middle))
                return middle;
            else if(!isBadVersion(middle+1))
                return firstBadVersionHelper(middle+1, end);
            else
                return firstBadVersionHelper(start, middle-1);
        }
    public:
        int firstBadVersion(int n) {
            return firstBadVersionHelper(0, n-1)+1;
            
        }
    };

Log in to reply
 

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