Input:[0,0,2,3,4,4,4,5], 5 Output:[7,8] Expected:[7,7] what's wrong with my codes?


  • 0
    X
    class Solution {
        public:
            vector<int> searchRange(int A[], int n, int target) {
                vector<int> result;
                int index = _search(A, 0, n-1, target);
                if (index == -1) {
                    result.push_back(-1);
                    result.push_back(-1);
                } else {
                    int start = index;
                    while (start >= 0) {
                        if (A[start] != target)
                            break;
                        start--;
                    }   
                    result.push_back(start+1);
                    int end = index;
                    while (index < n) {
                        if (A[end] != target)
                            break;
                        end++;
                    }   
                    result.push_back(end-1);
                }   
                return result;
            }   
            int _search(int A[], int start, int end, int target) {
                if (start <= end) {
                    int mid = (start + end) / 2;
                    if (A[mid] == target)
                        return mid;
                    else if (A[mid] < target)
                        return _search(A, mid+1, end, target);
                    else
                        return _search(A, start, mid-1, target);
                }   
                return -1; 
            }   
    };
    
        enter code here

  • 0
    O
                while (index < n) {
                    if (A[end] != target)
                        break;
                    end++;
                } 
    

    should be: while(end < n) ...


  • 0
    J

    When all the elements in the array is the same as the target, then your algorithm has the worst case time complexity of O(n) instead of O(log n).


Log in to reply
 

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