【剑指Offer】旋转数组的最小数字

Posted on | In ,

题目

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

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int minNumberInRotateArray(int[] array) {
    int left = 0;
    int right = array.length - 1;
    int mid = left;

    while (array[left] >= array[right]){
        if (right - left == 1) {
            mid = right;
            break;
        }

        mid = (left + right) / 2;

        if (array[mid] == array[left] && array[mid] == array[right])
            return minInOrder(array, left, right);
        else if (array[mid] >= array[left])
            left = mid;
        else if (array[mid] <= array[right])
            right = mid;
    }

    return array[mid];
}

private int minInOrder(int[] array, int left, int right){
    int min = array[left];

    for (int i = left + 1; i <= right; i++)
        min = Math.min(min, array[i]);

    return min;
}