time: O(logn), in 11111 0 11111 this case, worst case is almost O(n)
space: O(1)
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left)/2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else { // nums[mid] == nums[right]
right--;
}
}
return nums[left];
}
}