JZ11 旋转数组的最小数字

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

解法一：暴力法

直接遍历整个数组，找到第一个当前元素大于后一个元素的位置，那么后一个位置就是反转点，即最小值。

public int minNumberInRotateArray(int [] array) {
        if(array==null||array.length<=0){
            return 0;
        }
        for(int i=0;i<array.length-1;i++){
            if(array[i]>array[i+1]){
                return array[i+1];
            }
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11

复杂度分析：
时间复杂度：O(N)，遍历数组一次
空间复杂度：O(1)，不涉及额外内存空间

解法二：二分法

使用中间值和右值做对比，如果右值大于中间值，说明反转点在中间值以左，所以让right=mid;

如果右值小于中间值，说明反转点在中间值以右，所以让left=mid+1;

如果右值等于中间值，right–;

注意点：right=array.length-1而不是array.length，直接取的是右值作比较，防止下标越界。

判断的时候取右值和中间值做比较，相等的时候是 right–而不是left++。

public int minNumberInRotateArray(int [] array) {
    int left=0;
    int right = array.length-1;
    while(left<right){
        int mid=(left+right)/2;
        if(array[right]>array[mid]){
            right= mid;
        }else if(array[right]<array[mid]){
            left=mid+1;
        }else{
            right--;
        }
    }
    return array[left];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析：
时间复杂度：O(LogN)，二分查找O(logN)
空间复杂度：O(1)，不涉及额外内存空间

总结：
涉及数据结构：数组
涉及算法：二分法