旋转数组的最小数字【Java版】

1）O(n) 暴力扫描

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length==0)return 0;
        int min=array[0];
        for (int i=0;i<array.length;i++){
            if (array[i]<min)min=array[i]; 
        }
        return min;
    }
}  
//暴力查找，时间O(N)

2）二分法

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int len=array.length;
        if(len==0)return 0;
        int left=0;int right=len-1;//自己写区间的时候，尽量用“左闭右闭”区间，不然容易出错。（不要用左闭右开区间！！）
        while(left<right){
            if(array[left]<array[right]){//严格小于//说明区间里面没有“断层”，单调增/单调不减
                return array[left];
            }
            int mid=(left+right)/2;//左右区间内有“断层”的时候，需要探测mid位置的值
            //3种情况：大于小于等于（最好画个图）//最好是mid和right来比较；选mid和left来比较时，还需要再次分类判断（因为只有2个数时，mid和left重合）
            if(array[mid]>array[right])left=mid+1;
            else if(array[mid]<array[right])right=mid;
            else if(array[mid]==array[right])--right;//这种情况容易考虑不到，导致区间无法收敛
        }
        return array[right]; //此时只有一个元素，所以left==right
    }
}
//二分查找，平均时间O(logN)
//最坏情况（全部相等）时间复杂度O(N)