寻找旋转排序数组中的最小值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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

提示：
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

示例

例1

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

例2

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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，发现此题是一道二分的变形题，在此题中，我们只要知道除了原数组外，左边界都应该大于最小值以及大于等于右边界，在包含最小值的子数组也是一样的，此时我们就找到二分的条件了，让我们来看看具体如何实现的吧。

实现

public int findMin(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        int left = 0;
        int right = n - 1;

        // 此时数组等于原数组
        if (nums[left] < nums[right]) {
            return nums[left];
        }

        int mid = 0;
        // 数组中最小值肯定是小于左边界的，而左边界总是大于等于右边界的
        while (left < right) {
            mid = left + (right - left) / 2;

            // 此时mid前面所有元素可以舍去
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            // 此时mid后面的元素可以舍去
            else if (nums[mid] < nums[right]){
                right = mid;
            }
            // 此时中值与右边界相等，无法判断，但是可以将右边界左移一位，可以去重
            else {
                right -= 1;
            }
        }

        // 当左右边界合一时,即结果
        return nums[left];
    }