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

• 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);
}
};
``````

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