剑指Offer第11题——旋转数组中的最小值

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

一个有序数组旋转后，分成了两个有序的子数组，这样一个大数组相当于一定程度上是有序的。因此可以尝试使用二分法。mid = low + (high - low)/2，始终将mid和high处的值作比较。分三种情况。

• array[mid] > array[high] 此时mid肯定还处于左侧数组之中，要找的最小值在右侧数组中，最小值肯定在mid的右侧，所以可以直接把low移动到mid的下一个位置，即low=mid+1。
• array[mid] < array[high] 此时mid肯定处于右侧数组之中，要找的最小值可能为mid的值或者mid右边的值，所以high只能缩小到mid，不能缩小到mid-1。
• array[mid] == array[high]，此时无法分辨mid处于左半数组还是右半数组。比如{1, 0, 1, 1, 1}和{1, 1, 1, 0, 1}都是数组{0, 1, 1, 1, 1}的旋转数组。此时mid处和high处的值一样，若根据low缩小范围，对于{1, 0, 1, 1, 1}最小值将被跳过；如果根据high缩小范围，对于{1, 1, 1, 0, 1}最小值也会被跳过。所以此时只能放弃二分查找，既然mid处和high处的值相同，那么就让high--，让mid和high前面的值作比较。如果mid和high都是最小值，就算放弃了high也能在mid处找到最小值。

只要low<high（不含等于），就一直重复以上比较过程，一直比到low与high指向同一个元素，到low==high的时候退出，其实low == high时候还进入循环，也没有错，此时只会造成high--，而我们返回的是array[low]，值不会影响，但是何必进行这次无意义的比较呢。
PS：为什么要把mid和high作比较，而不能让mid和low作比较，试想如果最后范围缩小到剩下{1, 2}此时array[low] == array[mid]，如果low++就跳过最小元素了，此种情况可以写一个min(int low, int high)方法，直接返回[low, high]范围内的最小值。比起用high来和mid比较，麻烦了不少。

 public int minNumberInRotateArray(int [] array) {
        if (array==null || array.length == 0) {
            return 0;
        }

        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            // 此时mid一定在左半数组中，最小值在mid的右边
            if (array[mid] > array[high]) {
                low = mid + 1;
              // 此时mid一定在右半数组中，最小值在mid的左边或就是mid本身
            } else if (array[mid] < array[high]) {
                high = mid;
              // 暂时放弃二分查找，和前一个字符继续比较
            } else {
                high--;
            }
        }
        // low == high时推出循环并返回
        return array[low];
    }