LeetCode-154-寻找旋转排序数组中的最小值II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [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];
    }
}