旋转数组中最小数

原文链接 http://blog.csdn.net/qq_22329521/article/details/52966416

把一个数组最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。输入一个递增排序的数字的一个旋转数组，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}位{1,2，3,4,5}的一个旋转，求该数组的最小值

思路：最直观的解法并不难，从头到尾遍历数组一次，我们就能找到最小元素但是时间复杂度为O(n）

另一种思路，旋转之后的数组实际上是可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意最小的元素刚好是这两个字数组的分界线.在排序的数组中我们可以用二分查找发实现O(logn)安装旋转规则，第一个元素应该大于或者等于后一个元素（不一定)
特殊情况如果把排序数组的前面的0个元素搬到后面，这依然是数组的一个旋转，一旦发现数组中第一个数字小于最后一个数字们可以直接返回第一个数字
特殊情况数组{1,0,1,1,1}和数组{1,1,1,0,1}都可以看成递增数组{0,1,1,1,1}的旋转但是二分法不管用，只能使用顺序查找

public static int minNumberInRotateArray(int[] array) {
        if (array.length == 0) return 0;  
        int left = 0;   
        int right = array.length - 1;   
        int mid = left;   // 设置初始位置,可以当左侧小于右侧的时候，直接返回说明是第0个元素排到后面
        // 确保left在前面排好序的位置，right在后面排好序的位置
        while (array[left] >= array[right]) {
            // 当处理数据只有两个返回后一个结果
            if (right - left == 1) {
                return array[right];
            }
          
            mid = (left + right) / 2;
            // 如果三个数相等，顺序查找最小值
            if ((array[left] == array[mid]) && (array[left] == array[right]) && (array[mid] == array[right])) {
                return minNum(array, left, right);
            } else if (array[left] >= array[mid]) { 
                right = mid;
            } else {  
                left = mid;
            }
        }
        return array[mid];
    }

    private static int minNum(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;
    }