/*
问题：找旋转有序（增序）数组（含重复数）中的最小数
分析：
旋转后，会形成两个有序左右子数组，且左子数组的数一定比右子数组的数大(或等于)
如[2,2,2,0,1,1,2]
方法：二分查找，遇到相同数字时，left右移一位
平均O(logn),最坏O(n)
*/
class Solution
{
public:
int findMin(vector<int> &nums)
{
if(nums.empty()) return 0;
if(nums.size() == 1) return nums[0];
int res = nums[0];
int left = 0, right = nums.size() - 1;
if(nums[left] >= nums[right]) //若有旋转，由于有重复数字，故这里变为大于等于
{
while (left < right - 1)
{
int mid = (left + right) / 2;
if (nums[left] < nums[mid]) //若中间的数大，移动left指针到中间
{
res = min(res, nums[left]);
left = mid;
}
else if(nums[left] > nums[mid]) //若中间的数小，移动right指针到中间
{
res = min(res, nums[right]);
right = mid;
}
else //若left与mid指向数字相等，将left右移一位,略过相同数字
left++;
}//退出时，left = right -1,left指向左子数组的末尾或右子数组的开头
res = min(res, nums[left]);
res = min(res, nums[right]);
return res;
}
else //若无旋转
return nums[0];
}
};
