2021/4/9 寻找旋转排序数组中的最小值 II

题目描述

描述转载自力扣《154. 寻找旋转排序数组中的最小值 II》
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例1

输入：nums = [1,3,5]
输出：1

示例2

输入：nums = [2,2,2,0,1]
输出：0

解题思路

1. 对于数组最后一个元素 x 来说，数组中的最小值及其右边的所有元素的值必然小于等于 x，最小值左边的所有元素值必然大于等于 x。
   
2. 使用二分查找法查找最小值。定义 left、right 以及 两个指针的中间值 mid。我们分三种情况：
   • 如果 mid 小于 right，就说明最小值在 mid 上或 mid 的左边
     
   • 如果 mid 大于 right，说明最小值在 mid 右边
     
   • 如果 mid 与 right 值相等，有可能 mid 是最小值，也有可能不是最小值，尽管这是一句废话，但它说明了我们可以直接抛弃 right，因为如果 mid 真的是最小值，那也就不需要把 right 算进来了；如果 mid 不是最小值，那 right 也不会是，也可以抛弃。

Java 代码实现

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]) right = mid;
            else if (nums[mid] > nums[right]) left = mid + 1;
            else --right;
        }
        return nums[left];
    }
}