14 ms C++ binary search easy to understand


  • 0
    T
    vector<int> searchRange_helper(vector<int>* nums, int target, int leftpos, int rightpos) {
        int inputsize = rightpos - leftpos;
        
        if(inputsize <0 || (inputsize == 0 && (*nums)[leftpos]!= target)) return {-1, -1};
        if(inputsize == 0) return {leftpos,rightpos};
        
        int start = INT_MAX;
        int end = INT_MIN;
        int mid = (leftpos+rightpos);
        int midval = (*nums)[mid/2];
        
        if(midval > target){
            return searchRange_helper(nums, target, leftpos, mid/2 -1);
        }else if(midval < target){
            return searchRange_helper(nums, target, mid/2 +1, rightpos);
        }else{
            
            vector<int> left = searchRange_helper(nums, target, leftpos, mid/2 -1);
            start = left[0];
            if(start == -1) start = mid/2;
            
            vector<int> right = searchRange_helper(nums, target, mid/2 +1, rightpos);
            end = right[1];
            if(end == -1) end = mid/2;
            
            return {start,end};
        }
    }
    
    vector<int> searchRange(vector<int>& nums, int target) {
        int inputsize = nums.size();
        if(inputsize == 0 || (inputsize == 1 && nums[0]!= target)) return {-1, -1};
        if(inputsize == 1) return {0,0};
        
        return searchRange_helper(&nums, target, 0, inputsize-1);
    }

Log in to reply
 

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