剑指offer_11_旋转数组中的最小数字

描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素，排序的旋转数组定义如下：

如：{1,2,3,4,5}的一个旋转数组为{3,4,5,1,2} 该数组的最小值为1           

复制

初看题目我们最直观的解法并不难，遍历数组用俩个"指针"一前以后，当前面"指针"指向的元素比后面的"指针"指向的数组元素小时，这时我们就找到旋转数组中的最小元素，我们不难写出如下代码：

public static int findMin(int[] arr) {
    // 如果数组是只有一个元素 则不是旋转数组同时也防止下边的i+1越界
    if(arr == null || arr.length <= 1){
        return -1;
    }

    for (int i =0 ; i < arr.length -1; i++) {
        if (arr[i] > arr[i + 1]) {
            return arr[i + 1];
        }
    }
    return -1;
}           

复制

但是上面这种方法当数组的元素特别多时，效率是比较低的，不足以拿到offer，现在考虑用二分法对上面算法进行改良：

定义一个数组最左边的"指针"left和一个数组最右边的"指针"right，每次求俩个指针的中间值记为middle，如果left所对应的值要比middle小，那么说明数组还在递增中，最小值会在middle和right之间，这时候我们让left等于middle，继续用同样的方式缩小范围，如果middle要比right小，那么说明最小值在left和middle之间，让right等于middle，用同样的方式继续求下去，就能求到最小值啦。

public static int findMin(int []arr) {
    int left = 0;
    int right = arr.length;
    while(left < right) {
        int middle = (left + right) / 2;
        if (arr[left] < arr[middle]) {
            left = middle;
        // 如果遇到相同的元素 我们就只能用遍历了
        } else if(arr[left] == arr[middle]){
            for(int i = left; i <= middle; i++) {
                if(arr[i] < arr[middle]) {
                    return arr[i];
                }
            }
            return arr[left];
        } else{
            right = middle;
        }
        if (right - left == 1) {
            if(arr[right] > arr[left])
                return arr[left];
            else
                return arr[right];
        }
    }
    return  arr[left];
}           

复制

当left对应的元素与right对应的元素相等时，这是特殊情况，这里选择遍历去找最小值。