JZ4 二维数组中的查找

难度：简单

描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O(1) ，时间复杂度：O(logn)

举例

解题思路

本题的直观解法很简单，直接对数组进行一次遍历就可以找到最小值，复杂度为O(n)，但是显然这不是本题的意图所在，因为没有利用到任何旋转数组的特性。

进一步分析，如果整个数组是有序的，那我们一定会想到用折半查找来实现。对于旋转数组，我们发现，它实际上可以划分为两个排序的子数组，而且前面数组的元素都不小于后面数组的元素，并且最小值正好就是这两个数组的分界线，由此，我们可以得出以下解决方法。

首先用两个指针low和high分别指向数组的第一个元素和最后一个元素，然后可以找到中间元素mid。对于这个中间元素，有以下两种情况：

（1）该元素大于等于low指向的元素，此时最小的元素说明在mid的后面，可以把low=mid；

（2）中间元素小于等于high指向的元素，那么最小元素在mid之前，可以high=mid。特别注意：这里不要+1或者-1，因为只有这样才能保证low始终在第一个数组，high始终在第二个数组。依次循环，当最后low和high相差1时，low指向第一个数组的最后一个，high指向第二个数组的第一个（即为我们要找的最小值）。

很明显，以上查找的时间复杂度为O(logN)。

除此之外，本题还有两个特殊情况：

将数组前0个元素移动到后面（相当于没有旋转，数组整体有序）。明显我们上面的分析没有包含这种情况，需要特殊处理，方法也很简单，将第一个元素和最后一个元素相比，若第一个元素小于最后一个元素，则说明最小值就是的第一个元素，可以直接返回。

首尾指针指向的数字和中间元素三者都相等时，无法判断中间元素位于哪个子数组，无法缩小问题规模。此时，只能退而求其次，进行顺序查找。

编程实现（java）

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        // 特殊情况判断
        if (array.length== 0) {
            return 0;
        }
        // 左右指针i j
        int i = 0, j = array.length - 1;
        // 循环
        while (i < j) {
            // 找到数组的中点 m
            int m = (i + j) / 2;
            // m在左排序数组中，旋转点在 [m+1, j] 中
            if (array[m] > array[j]) i = m + 1;
            // m 在右排序数组中，旋转点在 [i, m]中
            else if (array[m] < array[j]) j = m;
            // 缩小范围继续判断
            else j--;
        }
        // 返回旋转点
        return array[i];
    }
}

结果