旋转数组的最小数字

旋转数组的最小数字

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

思路：

先排除两种特殊的情况

1. 数组的长度为1，直接返回最小值
2. 假如最右边的大于最左边的，最左边的肯定最小，返回最左边的元素

然后通过二分法来缩小查找范围，缩小范围的思路下面代码中有

代码：

public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length-1;
        int mid = 0;
        if(array.length == 1) {
            return array[0];
        }
        if(array[left] < array[right]) {
            return array[left];
        }
        while(left < right-1) {
            mid = left + (right - left) / 2;
            //中间的大于最左边的或者中间的大于最右边的，都可以锁定最小值在右边
            if(array[mid] > array[left] || array[mid] > array[right]) {
                left = mid;
            }else if(array[mid] < array[left]){//可以锁定最小值在左边
                right = mid;
             }else{//最左边的与最右边的相等，随便哪边缩小一位
                right = right-1;//left = left + 1
            }
        }
        if(array[left] < array[right]) {
            return array[left];
        }
        return array[right];
    }