Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
该题比上题存在重复数字，所以另加一项处理，当遇到重复时候，忽略该值，然后接着使用上题的逻辑处理。代码如下。
int find(int *nums,int s,int t)
{
if(s==t)
return nums[s];
if(nums[s]==nums[t])
{
return find(nums,s+1,t);
}
if(nums[s]<nums[t])
return nums[s];
if(s==t-1)
{
int min=nums[s];
if(min>nums[t])min=nums[t];
return min;
}
int mid=(s+t)/2;
if(nums[mid]>nums[t])
return find(nums,mid,t);
return find(nums,s,mid);
}
int findMin(int* nums, int numsSize) {
int ans= find(nums,0,numsSize-1);
// printf("%d\n",ans);
return ans;
}
