每日一题，提升自己。今天分享一道关于旋转数组中查找最小值的题目，且听我细细道来。

数组 - 旋转数组中查找最小值

1. 题目描述

        把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例：

示例1：

输入：[3,4,5,1,2]

输出：1

示例2：

输入：[2,2,2,0,1]

输出：0

2. 解题思路

        首先，数组是一个有序数组的旋转数组，从这个条件可以看出，输入的数组是有大小规律的，只是分成了两部分相同规律的。既然是有序数组，那么就可以使用二分查找利用存在的规律来查找结果。

复杂度：

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。

3. 算法流程

1. 初始化下标 left=0 和 right=nums.length-1。当left<right时，证明查找还没有结束。
2. 每次计算中见下标 mid = (right + left) / 2，这里的除法时取整运算，不能出现小数。
3. 当nums[mid] < nums[right]时，说明最小值在[left, mid]区间中，则令right = mid，用于下一轮计算。
4. 当 nums[mid] > nums[right] 时，说明最小值在 [mid, right] 区间中，则令 left = mid + 1，用于下一轮计算。
5. 当 nums[mid] == nums[right] 时，无法判断最小值在哪个区间之中，此时让 right--，缩小区间范围，在下一轮进行判断。
6. 最后返回nums[left]的值。

问：为什么是 right--缩小范围而不是left++？

答：因为数组是升序的额，所以最小值一定靠近左侧，而不是右侧。

比如，当存在 [1,2,2,2,2] 这种情况时，left = 0，right = 4，mid = 2，数值满足 numbers[mid] == numbers[right] 这个条件，如果 left++，则找不到最小值

4. 代码实现

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static int minRotateArray(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;
        }else {
            right--;
        }
    }
    return nums[left];
}