# One simple and clear method with O(1) space and worst O(n) time

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

• This is a perfect answer, thanks for share.

• so how do we know that, the input array got rotated only once ?

• Why it always return num[j] at last? I couldn't understand it.

• nice iterative solution!

• Great solution, thx very much!

• 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+((right-left)>>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];
}``````

• can anybody please explain me, why this is require.

if(num[i]==num[mid]){//linear complexity
i++;
j--;
}

• To get a O(n) time solution, binary search is not necessary. Read my easy solution here