public int findMin(int[] nums) {
int l = 0, r = nums.length1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < nums[r]) {
r = mid;
} else if (nums[mid] > nums[r]){
l = mid + 1;
} else {
r; //nums[mid]=nums[r] no idea, but we can eliminate nums[r];
}
}
return nums[l];
}
Super simple and clean Java, binary search.

hi, wujin, would you mind shedding some light on how you come up with the idea of comparing with the upper bound to decide the action, instead of the lower bound or nums[0]? not that straightforward for me though. Looking back it is a great solution, but how you find out comparing with the upper bound is the best way to go?

@fabian4 this is the same as searching in rotated array II . the big O runtime will be linear considering worst case of all duplicates. You cant do better than O(N) in worst case.