My simple and easy-understanding solution with O(logn) time complexity


  • 1
    B
    class Solution {
    public:
        int searchStart( int A[], int start, int end, int target ) {
            while ( start <= end ) {
                int mid = ( start + end ) / 2;
                if ( A[mid] == target )
                    end = mid-1;
                else
                    start = mid+1;
            }
            return start;
        }
        int searchEnd( int A[], int start, int end, int target ) {
            while ( start <= end ) {
                int mid = ( start + end ) / 2;
                if ( A[mid] == target )
                    start = mid+1;
                else
                    end = mid-1;
            }
            return end;
        }
        vector<int> searchRange(int A[], int n, int target) {
            int start = 0; 
            int end = n-1;
            while ( start <= end ) {
                int mid = (start + end ) / 2;
                if ( A[mid] < target )
                    start = mid+1;
                else if ( A[mid] > target )
                    end = mid-1;
                else {
                    int startIndex = searchStart( A, start, mid, target );
                    int endIndex = searchEnd( A, mid, end, target );
                    vector<int> v;
                    v.push_back(startIndex);
                    v.push_back(endIndex);
                    return v;
                }
            }
            vector<int> v;
            v.push_back(-1);
            v.push_back(-1);
            return v;
        }
    };

Log in to reply
 

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