剑指Offer_#11_旋转数组的最小数字

Contents

• • 题目
  • 思路分析
    • 二分查找
  • 解答

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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

思路分析

旋转操作将原本的一个有序数组分割为两个有序数组，分别称之为左有序数组和右有序数组。
所谓的最小数字其实就是旋转点的数字，或者说右有序数组的第一个数字，其下标用pivot表示。

整体的思路是二分查找，使用两个指针，通过比较，不断地缩小范围，最后两个指针相遇，指向的就是要找的最小数字。

二分查找

初始化左右指针为数组的开头(i)和结尾(j)，然后取中间点(m)，判断中间点是位于左有序数组，还是右有序数组，判断条件是：

• numbers[m] > numbers[j]
  • 说明中间点m位于左有序数组。要找的pivot在当前m的右边，所以把左边界右移，即执行i = m + 1。这里加1是因为，number[m]大于某个数字（number[m]或者number[j]),所以m绝不可能是最小数字，直接排除掉。
• numbers[m] < numbers[j]
  • 说明中间点m位于右有序数组。要找的pivot在当前m的左边，所以把右边界左移，即执行j = m。这里没有像上边一样减一是因为，pivot是一定属于右有序数组的，如果减一，可能就错过pivot数字了。
• 特殊情况：numbers[m] == numbers[j]
  • 不好判断中间点m到底是位于左有序数组还是右有序数组，这里就可以直接右移左边界一位，即执行j--。为什么可以这么做，是因为这样做并不会错过pivot,将pivot排除在外。具体论证如下。

分情况讨论： m位于左有序数组，m位于右有序数组。

1. 若m位于左有序数组，那么pivot在m的右边。继续分类讨论:j就是pivot,j不是pivot.
   a) j就是pivot,这时j--就把pivot错过了,直接将范围缩小到左有序数组。举例说明：在[1,1,1,2,1]当中，numbers[m(2)] == numbers[j(4)],pivot与j重合。这隐含了一个信息，也就是numbers[j]<=numbers[i]<=numbers[m]（将pivot还原到数组开头，得到的数组是有序数组），又有numbers[m]==numbers[j],则说明numbers[i]==numbers[i+1]==...==numbers[m]==numbers[j]。那么之后一定是将j逐渐左移，进入到[i,m]范围内，最终定位到的值也一定与pivot相等，不会错过pivot。
   b) j不是pivot,pivot又在m右边，那执行j--正好是在缩小范围，也不会错过pivot.
2. 若m位于右有序数组，那么pivot在m的左边。应该左移右边界j,直接j--是不会错过pivot的。之后继续进行二分搜索，必然是把范围逐渐左移。

为什么选择numbers[j]作为判断标准？ 原因是numbers[j]一定位于右有序数组中，但numbers[i]不一定位于左有序数组中，例如数组[1,2,3,4,5]只有右有续数组，pivot==0。
以下举两种不同测试用例进行分析。

• 不存在相等数字

不存在相等数字

这时，左有序数组的任何一个数大于右边界数。
右有序数组的任何一个数小于右边界数。

• 存在相等数字

存在相等数字

这时，左有序数组任何一个数大于等于右边界数。
右有续数组任何一个数小于等于右边界数。

综上，在中间数不等于numbers[j]的时候，可以以numbers[j]作为判断标准。

解答

class Solution {
    public int minArray(int[] numbers) {
        int i = 0,j = numbers.length - 1;
        while(i < j){
            int m = (i+j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[j];
    }
}