旋转数组的最小值

旋转数组的最小值

所谓旋转数组，即是递增有序数组旋转右移动若干位得到的数组，这里的右移和java里的>>>有点不同，像是汇编里的那个移动，流水灯的那个移动
比如：

1,2,3,4,5,6---->4,5,6,1,2,3

因为这个可以是看成是已经有序的递增数组，所以可以用二分法，

1. 选定一个中间数，若右边的数小于中间数，说明那个最小的数字应该处于中间的数字到右边的那个数字之间。包括边界的两个数字;
   
   
2. 选定一个中间数，如果左边的数字大于中间的数字，说明最小的的那个数字应该在处于左边的数字到中间的数字之间。
3. 情况3就比较奇葩了，如这个数组{5,1,2,3,5,5,5,5,5,5,5}
   第一次取的中间值是5，然后他和左边和右边的值都是一模一样的，导致根本就不知道是属于情况1还是2，所以这个时候就只能暴力遍历了。。当然暴力遍历也不能放弃之前筛选的成果，所以加上了左右边界。

public static int findSmallestNumber(int[] array){
        //左边界的下标
        int left = 0;
        //右边界的下标
        int right = array.length - 1;
        
        for(int i = array.length ; i > 0 ; i = i / 2){
            int middle = array[(left + right) / 2];
            //情况1
            if(array[right] < middle){
                left = (left + right) / 2;
            //情况2
            }else if(array[left] > middle){
                right = (left + right) / 2;
            }else{
                //这里就是情况3
                return minInOrder(array, left, right);
            }
               //最后当左右只差1的时候，最小的就是两者其一
            if(right - left == 1){
                if(array[right] > array[left]){
                    return array[left];
                }else{
                    return array[right];
                }
            }
        }
        return -1;
    }
    
    private static int minInOrder(int[] array , int left , int right){
        int min = array[left];
        for(int i = left + 1; i <= right ; i++){
            if(array[i] < min){
                min = array[i];
            }
        }
        return min;
    }