Share my strictly O(logn) solution -- recursive method C++


  • 0
    U
        vector<int> searchAppear(int A[], int l, int r, int target){
        //if [l..r] is not a valid search range, return an empty range
        if(l > r || A[l] > target || A[r] < target)
            return vector<int>();
        
        //else do binary search on [l..r]
        int mid = l + (r - l) / 2;
        if(A[mid] == target){
            vector<int> result(2, mid);
            vector<int> left = searchAppear(A, l, mid - 1, target);  //find target in [l..mid-1]
            vector<int> right = searchAppear(A, mid + 1, r, target); //find target in [mid+1..r]
            //combine the three range
            if(!left.empty())
                result[0] = left.front();
            if(!right.empty())
                result[1] = right.back();
            return result;
        }
        if(A[mid] > target)
            return searchAppear(A, l, mid - 1, target);            
        else
            return searchAppear(A, mid + 1, r, target);              
                         
    }
    
    
    vector<int> searchRange(int A[], int n, int target){
        //do binary search on [0..n-1]
        vector<int> result = searchAppear(A, 0, n - 1, target);
        if(result.empty()) //if target is not found, return[-1,-1]
            return vector<int>(2, -1);
        return result;
    }
    

    Idea is explained by comments.


Log in to reply
 

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