题目描述

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

解题思路

1. 复杂度，因为题目要求就是找到数组中的最小值，所以可以遍历一遍，找到这个值。
2. 复杂度，因为经过一次旋转之后，这两段数组都是有序的，就可以使用二分查找的方法。

我们可以设定两个下标 low = 0 和 high = len -1，并设定 mid = (low + high)/2 得到数组中间的元素。如果中间的元素大于或者等于 low 下标对应的元素，此时数组中最小的元素应该位于该元素的后面，我们可以把 low 下标指向该中间元素；如果中间元素小于或者等于 high 下标对应的元素，此时该数组中最小的元素应该位于该中间元素的前面。我们就可以把 high 下标更新到中位数的下标。
不管是更新 low 还是 high，我们的查找范围都会缩小为原来的一半，接下来我们再用更新的下标去重复新一轮的查找，直到找到旋转数组的最小值。

代码实现

import java.util.ArrayList;
public class Solution {
    public static int minNumberInRotateArray(int[] array) {
        int len = array.length;
        if (len == 0)
            return 0;
        int low = 0;
        int high = len - 1;
        int mid = low;
        while (array[low] >= array[high]) {
            //左边比右边下标为1时候找到目标值
            if (high - low == 1) {
                mid = high;
                break;
            }
            mid = (low + high) / 2;
            if (array[mid] >= array[low]) {     //当中间值比左边值大的时候说明最小值还在后面
                low = mid;
            } else if (array[mid] <= array[high]) {     //当中间值比左边值小的时候说明最小值在前面
                high = mid;
            }
        }
        return array[mid];
    }
    public int minNumberInRotateArray2(int [] array) {
        if(array==null){
            return 0;
        }
        int len=array.length;
        int ans=array[0];
        for(int i=1;i<len;i++){
            if(array[i]<ans){
                ans=array[i];
            }
        }
        return ans;
    }
}