C++ 12ms divide and conquer, super easy to understand for beginner


  • 0
    B

    three help function
    find() using binary search to find target
    once find target, we use another two help function to find left and right boundary

    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) 
        {
            if(nums.empty()) return vector<int>{-1,-1};
            return find( nums, 0, nums.size()-1, target );
        }
        
    //help function to find target
        vector<int> find(vector<int>& nums, int l, int r, int target)
        {
            if(l>r || target<nums[l] || target>nums[r]) return vector<int>{-1,-1};
            if(l==r) return nums[l]==target ? vector<int>{l,l} : vector<int>{-1,-1};
            int mid = (l+r)/2;
            if(nums[mid]==target) return vector<int>{findLeft(nums,l,mid,target), findRight(nums,mid,r,target)};
            if(nums[mid]>target) return find( nums, l, mid-1, target);
            return find(nums,mid+1,r,target);
        }
        
    //help function to find left bounary
        int findLeft(vector<int>& nums, int l, int r, int target)
        {
            while(l<r)
            {
                if(nums[l]==target) return l;
                int mid = (l+r)/2;
                if(mid==l) return r;
                if(nums[mid]==target) r = mid;
                else l = mid+1;
            }
            return l;
        }
        
    //help function to find right boundary
        int findRight(vector<int>& nums, int l, int r, int target)
        {
            while(l<r)
            {
                if( nums[r]==target) return r;
                int mid = (l+r)/2;
                if(mid==l) return l;
                if(nums[mid]==target) l = mid;
                else r = mid - 1;
            }
            return l;
        }
    };
    

  • 0

    @beetlecamera It's really had to read your code, though it might be good. So please always remember to format your code properly using ``` the block formatting symbol. Many thanks!


Log in to reply
 

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