面试题11:旋转数组中的最小数字

要考虑特殊情况：
1、数组没被旋转
2、low,mid,high所在位置的值相同

    public int minNumberInRotateArray(int [] array) {
    
        int low=0,high=array.length-1,mid=0;
        // 如果没有做旋转，则直接返回a[0]
        if(array[low]<array[high])return array[low];
        // 如果有旋转，则左边[low,indx]是比[indx+1,high] 大的递增序列
        // 找到那个indx使得刚好 a[indx]>a[indx+1]，a[indx+1]就是最小值
        // 必须是<=，因为有可能两个相同的数字，旋转后被分开
        while(array[low]>=array[high]){
            // 如果low和high相邻，则右边的小
            if(low+1==high)
                return array[high];
            mid = (low+high)/2;
            // 左边有序
            if (array[low]==array[mid]&&array[mid]==array[high]){
                int min = array[low];
                for(int i=low+1;i<high;i++){
                    if(array[i]<min)
                        min = array[i];
                }
                return min;
            }
            if(array[low]<=array[mid])
                low = mid;
            // 右边有序
            else 
                high=mid;
        }
        return array[mid];
    }