Accepted C++ recursive logN worst case solution


  • -3
    Z

    class Solution {
    public:

    int find_min(vector<int> &a, const int left, const int right) {
        int L = left;
        int R = right;
        while (R-L > 1) {
            const int M = (R+L)/2;
            if (a[L] < a[R])
                return a[L];
            if (a[L] > a[R]) {
                if (a[R] >= a[M])
                    R = M;
                else /*  a[L] <= a[M] */
                    L = M;
                continue;
            }
            /* a[L] == a[R] */
            if (a[L] < a[M])
                L = M;
            else if (a[L] > a[M])
                R = M;
            else { /* a[L] == a[M] == a[R] */
                const int lmin = find_min(a,L,M);
                const int rmin = find_min(a,M,R);
                return ::std::min(lmin,rmin);
            }
        }
        return ::std::min(a[L],a[R]);
    }
    
    int findMin(vector<int> &a) {
        if (a.size() == 1)
            return a[0];
        find_min(a,0,a.size()-1);
    }
    

    };


  • 1
    L

    the worst case is all elements are the same.

    So this part :

    const int lmin = find_min(a,L,M);
                const int rmin = find_min(a,M,R);
    

    will result in an overall O(N) runtime.


Log in to reply
 

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