题目：Find Minimum in Rotated Sorted Array
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.
You may assume no duplicate exists in the array.
解析： 使用二分法找到最小元素，因为没有重复元素所以直接二分
代码：
class Solution { public: int findMin(vector<int>& nums) { int left=0; int right=nums.size()-1; int mid=0; if (nums[0]<=nums[nums.size()-1]) { return nums[0]; } while(left<right) { mid=(left+right)/2; // if (nums[mid]) if (nums[mid]>nums[nums.size()-1]) { left=mid+1; } else if(nums[mid]<nums[nums.size()-1]) { right=mid; } } return nums[left]; } }; Find Minimum in Rotated Sorted Array II
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.
解析：带有重复的元素，当mid的元素和左右两端的元素都相同时，无法判断下次二分时mid的位置应该是left,right,需要打破这种平衡，
然后把right--
代码：
class Solution { public: int findMin(vector<int>& nums) { int left=0; int right=nums.size()-1; int mid=0; if (nums[0]<nums[nums.size()-1]) { return nums[0]; } while(left<right) { mid=(left+right)/2; // if (nums[mid]) if (nums[mid]>nums[right]) { left=mid+1; } else if(nums[mid]<nums[right]) { right=mid; } else if(nums[mid]==nums[right]&&nums[mid]==nums[left]) { right--; } else if(nums[mid]==nums[right]&&nums[mid]!=nums[left]) { right=mid; } } return nums[right]; } };
