题目：

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

这道题最简单的方法当然是直接遍历，然后找出最小的即可，时间复杂度是O(n)。但是这种方法并没有利用到旋转数组的特性，更好的方法是用类似于“二分查找”的方法。

旋转数组是有原先的有序数组做一定处理得到的，所以旋转数组以最小元素分割，两边都具有有序性，根据这个特性可以不断缩小查找的范围。

类似于二分查找，不断比较中间的值mid和最右边的值hi，如果mid大于hi，说明最小元素肯定在这两个数之间，也即右边；如果mid等于hi，那么我们无法判断最小元素在哪一边，只能按照顺序查找，将hi减一；如果mid小于hi，说明最小元素肯定在另外一边，也即左边，这个时候只需要更新一下hi即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0) {
            return 0;
        }
        int lo = 0, hi= array.length - 1;
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (array[mid] > array[hi]) {
                lo = mid + 1;
            } else if(array[mid] == array[hi]) {
                hi = hi - 1;
            } else {
                hi = mid;
            }
        }
        return array[lo];
    }
}

上述思路最佳的时间复杂度是O(logn)，最坏复杂度是O(n)，这道题算是二分查找的一个变形。