旋转数组里的最小元素

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

简单解答

旋转前的数组有序递增，最小元素在数组开头处，旋转之后数组分为两个有序递增的数组，最小元素处在数组的中间。我们可以从头往后扫描，遇到最小元素前，后一个元素总是大于前一个元素，如果不是，那就找到了最小元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int minNumberInRotateArray(int[] array) {
    if (array.length == 0) {
        return 0;
    }

    // 往后扫描，遇到递减则说明找到最小元素。
    for (int i = 0, head = 0; i < array.length; i++) {
        if (i + 1 < array.length) {
            if (array[i + 1] < array[i])
                return array[i + 1];
        }
    }

    return array[0];
}

该算法简单易懂，缺点也很明显：复杂度高达O（N）,一个长度为十亿的数组估计得扫描十亿次才能找到。

优化解答

首先我们可以建立一个概念，那就是，本来的数组是有序的，旋转后的数组分段有序，且最后一个元素肯定小于等于第一个元素，我们可以利用这一点来采用二分查找算法。
使 left 指向旋转数组最左边的元素，使 right 指向旋转数组最右边元素，mid 指向中间元素。如果中间元素大于 array[left]，那就说明最小元素在中间元素右边，否则就在左边，前一种情况我们令 left 指向 mid，后一种情况我们令 right 指向 mid，这样扫描完毕之后，left 会紧紧挨着 right，且 left 指向最大的元素，right 指向最小的元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minNumberInRotateArray(int[] array) {
    if (array.length == 0)
        return 0;

    int left = 0, right = array.length - 1;
    int mid;

    while (array[left] >= array[right]) {
        mid = (left + right) / 2;

        // 中间元素大于最左边的元素，说明中间元素在前面的数组里头，最小元素在后面。
        if (array[mid] >= array[left]) {
            left = mid;
        } else if (array[mid] < array[left]) {
            right = mid;
        }

        if (left + 1 == right)
            break;
    }

    return array[right];
}

这样一来，复杂度可以降到 O(LogN)。