假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5]
输出: 1
示例 2：
输入: [2,2,2,0,1]
输出: 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
解题思路
采用二分法，用左右索引逐步缩小范围，主要利用中间值与右索引所指值作比较
如果中间值大于右索引值，则最小值一定在(mid, right]中
如果中间值小于右索引值，则最小值一定在[left, mid]中
如果中间值等于右索引值，此时无法确定中间值与最小值的位置关系
比如[6, 1, 2, 2, 2]的最小值在中间值左边
而[3, 3, 1, 3]的最小值在中间值右边，所以这种情况只能让右索引往左逐步靠近
代码
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--;
}
}
return nums[right];
}
}
