class Solution {
public:
int findMin(vector<int> &num) {
if(num.empty())
return 0;
int i=0,j=num.size()1;
while(i<j)
{
int mid=(i+j)/2;
if(num[j]<num[mid]){
i=mid+1;
}
else if(num[mid]<num[j]){
j=mid;
}
else{//num[mid]==num[j]
if(num[i]==num[mid]){//linear complexity
i++;
j;
}
else
j=mid;
}
}
return num[j];
}
};
One simple and clear method with O(1) space and worst O(n) time


there maybe a slightly better one, early termination if no rotation. thanks to bandi's solution, I modified the code a little.
int findMin(vector<int>& nums) { int left=0, right=nums.size()1; while(nums[left]>=nums[right] && left<right) { int mid=left+((rightleft)>>1); if(nums[mid]>nums[right]) left=mid+1; else if(nums[mid]<nums[right]  nums[mid]!=nums[left]) right=mid; else { ++left, right; } } return nums[left]; }

To get a O(n) time solution, binary search is not necessary. Read my easy solution here
https://leetcode.com/discuss/100071/mosteasyanswer8msnobinarysearch

@drunoboy when the input is [2 3 2 2 2],
num[i]=num[0] = 2
num[j]=num[4] = 2
num[mid]=num[2] = 2
we cannot know how many same nums there, so i++ j