C++ solution with one pass binary search


  • 0
    D
    class Solution {
    public:
        vector<int> search(int A[], int start, int end, int target){
            vector<int> range(2, 0);
            range[0] = -1;
            range[1] = -1;
            if(end == start){
                if(A[start] == target){
                    range[0] = start;
                    range[1] = end;
                }
                return range;
            }
            int middle = (start + end) /2;
            if(A[middle] > target){
                if(middle > start){
                    range = search(A, start, middle-1, target);
                }
            }else if(A[middle]<target){
                if(middle < end){
                    range = search(A, middle+1, end, target);
                }
            }else{
                range[0] = middle;
                if(middle > start){
                    vector<int> newRange = search(A, start, middle-1, target);
                    if(newRange[0] != -1){
                        range[0] = newRange[0];
                    }
                }
                range[1] = middle;
                if(middle < end){
                    vector<int> newRange = search(A, middle+1, end, target);
                    if(newRange[0]!=-1){
                        range[1] = newRange[1];
                    }
                }
            }
            return range;
        }
    
        vector<int> searchRange(int A[], int n, int target) {
            vector<int> range(2, 0);
            range[0] = -1;
            range[1] = -1;
            if(n == 0){
                return range;
            }
            return search(A, 0, n-1, target);
        }
    };

  • 0
    G

    I think the recursion implement of the binary search may slow down the program, because the recursion always consumes more resources than loops.


Log in to reply
 

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