C++ 4ms divide and conquer, super easy to understand


  • 0
    B

    use two help functions to search in rotated and unrotated array.

    do a cut in the middle, the array would be divided into two arrays, one is rotated and one is unrotated. Then we can keep cutting by calling help function recursively.

    class Solution {
    public:
        int search(vector<int>& nums, int target) 
        {
            if(nums.empty()) return 0;
            return help1( nums, 0, nums.size()-1, target );
        }
        
        //help function to search in rotated array
        int help1(vector<int>& nums, int l, int r, int target )
        {
            if(l>r) return -1;
            if(l==r) return nums[l]==target ? l : -1;
            int mid = (l+r)/2;
            if(nums[mid]==target) return mid;
            if(nums[l]<=nums[mid])
            {
                if(target >= nums[l] && target < nums[mid])
                    return help2(nums, l, mid-1, target);
                else
                    return help1(nums, mid+1, r, target);
            }
            else
            {
                if(target > nums[mid] && target <= nums[r])
                    return help2(nums, mid+1, r, target);
                else
                    return help1(nums, l, mid-1, target);
            }
        }
        
        //help function to search in unrotated array
        int help2(vector<int>& nums, int l, int r, int target )
        {
            if(l>r) return -1;
            if(l==r) return nums[l]==target ? l : -1;
            int mid = (l+r)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]>target) return help2(nums, l, mid-1, target);
            else return help2(nums,mid+1,r,target);
        }
    };
    

Log in to reply
 

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