剑指 Offer 11. 旋转数组的最小数字

难度简单236收藏分享切换为英文接收动态反馈
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

方案1

解题思路

遍历一边，找一个最小的，返回即可。

解题代码

    public int minArray(int[] numbers) {
       int min = Integer.MAX_VALUE;
        for (int number : numbers) {
            min = Math.min(min,number);
        }
        return min;
    }

方案2

解题思路

例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

给定的数组是有序的，所以是有规律的，可以使用二分查找的办法，可以增加效率。

时间复杂度：O（longn），空间复杂度：O（1）

算法流程：

1、初始化left和right
2、每次计算中间下标 mid = （right + left ） / 2；注：这里除法必需为整数，不能出现小数，因为是求的下标。
3、当numbers[mid] < numbsers[right]时，说明最小值在[left,mid]区间，则令right=mid，继续下一轮查找；
4、当numbers[mid] > numbers[left]时，说明最小的值在[mid,right]区间，则令left=mid+1，继续下一轮查找；
5、当numbers[mid] == numbers[right]时，无法判断最小值在哪个区间之中，此时让right—，缩小区间范围，继续下一轮查找；
- 这里为什么使用right—？而不是left++呢？
  - 因为数组时升序的，所以最小值一定靠近左侧，而不是右侧；
  - 比如：当存在[1,2,2,2,2]这种情况时，left=0，right=4，mid=2，数值满足numbers[mid] == numbers[right]这个条件，此时就无法判断在左⬅️区间，还是右➡️区间。如果left++的话，就会错过小的数字，永远找不到最小的数，所以此时应该right—。
6、最终，left就是最小值的坐标，返回numbers[left]即可。

解题代码

public int minArray(int[] numbers) {
    int left = 0;
    int right = numbers.length - 1;
    while ( left < right ){
        int mid = (left + right) / 2;
        if( numbers[mid] < numbers[right] ){
            right = mid;
        }else if(numbers[mid] > numbers[right]){
            left = mid + 1;
        }else {
            right--;
        }
    }
    return numbers[left];
}