Is my solution O(log n)


  • 0
    A
    class Solution
    {
    public:
    vector<int> searchRange(int A[], int n, int target)
    {
        vector<int> v;
        int l , r ;
        int i = binSearch(A, 0, n - 1, target);
        if (i == -1)
        {
            v.push_back(-1);
            v.push_back(-1);
            return v;
        }
        else
        {
            l = i;
            r = i;
        }
        util(A, 0, n - 1, l, r, target);
        v.push_back(l);
        v.push_back(r);
        return v;
    
    }
    
    //l is used for current value of left bound and right is used for current value of right bound
    //we pass l and  r  by reference so as to update it in the  recursive calls if needed
    void util(int A[], int s, int e, int &l, int &r, int target)
    {
        int i = binSearch(A, s, e, target);
        if (i == -1)
            return;
        if (i < l)
            l = i;
        if (i > r)
            r = i;
    
        //We check the sub arrays either side of element so as to see whether they contain the target value
        util(A, s, i - 1, l, r, target);
        util(A, i + 1, e, l, r, target);
    
    }
    
    int binSearch(int A[], int first, int last, int target)
    {
        int middle = (first + last) / 2;
    
        while ( first <= last )
        {
            if ( A[middle] < target )
                first = middle + 1;
            else if ( A[middle] == target )
            {
                return middle;
                break;
            }
            else
                last = middle - 1;
    
            middle = (first + last) / 2;
        }
        if ( first > last )
            return -1;
    
    
    }
    
    };

Log in to reply
 

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