java实现旋转数组的最小数字

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

array表示递增排序旋转数组，使用left和right指针分别代表数组的左边界和右边界，数组中间元素的下标mid = (left+right)/2。

一个标准的递增排序旋转数组，总是有array[left] >= array[right]，当array[left] < array[mid]时，说明最小元素在mid右侧，使left = mid；array[left] > array[mid]时，最小元素在mid左侧，使right = mid。直到left和right相邻时，array[right]即是最小元素。。但有以下两种特殊情况：

第一种，即数组旋转后跟没有旋转一样，即array[left] < array[right]，此时array[left]为最小元素。

第二种，array[left] == array[right] == array[mid]，此时最小元素可能在mid左侧，也可能在右侧。因此，此时只能遍历left和right之间的数据找出最小元素。

代码如下：

public class Min {
    /**
     *
     * @param array 一个递增排序数组的旋转
     * @param length 数组长度
     * @return 返回最小值
     */
    private static int min(int[] array,int length){
        if (array == null || length == 0){
            throw new NullPointerException("array is empty");
        }
        int left = 0;
        int right = length - 1;
        //第一个元素大于最后一个元素，说明该数组为旋转的
        while (array[left] >= array[right]){
            //前后指针相邻，即array[right]是最小元素
            if (right - left == 1){
                return array[right];
            }
            int mid = (left + right)/2;

            //中间元素==左边界元素==右边界元素，无法确定最小元素在中间元素的左侧还是右侧，只能通过遍历求得最小元素
            if (array[left] == array[mid] && array[left] == array[right]){
                return minInOrder(array,left,right);
            }
            //中间元素大于左边元素，最小元素在中间元素的右侧，否则最小元素在中间元素左侧
            if (array[mid] > array[left]){
                left = mid;
            }else {
                right = mid;
            }
        }
        //第一个元素小于最后一个元素，说明该数组非旋转的，因此直接返回第一个元素
        return array[left];
    }

    /**
     *
     * @param array 一个递增排序数组的旋转
     * @param left 左边界
     * @param right 右边界
     * @return 返回最小值
     */
    private static int minInOrder(int[] array,int left,int right){
        int result = array[left];
        for (int i = left+1;i < right;++i){
            if (result > array[i]){
                result = array[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] a = {3,4,5,1,2};
        System.out.println(min(a,a.length));

        int[] b = {5,1,2,3,4};
        System.out.println(min(b,b.length));

        int[] c = {1,2,3,4,5};
        System.out.println(min(c,c.length));

        int[] d = {3,4,5,6,2,3};
        System.out.println(min(d,d.length));

        int[] e = {4,4,4,3,4};
        System.out.println(min(e,e.length));

        int[] f = {4,1,2,3,4,4,4};
        System.out.println(min(f,f.length));

        int[] g = {1,0,1,1,1};
        System.out.println(min(g,g.length));

        int[] h = {1};
        System.out.println(min(h,h.length));
    }
}

在没有加入第二种情况的代码（23-25行）时，输入数组e，输出的结果为4；输入数组h，程序陷入死循环。而输入数组g，输出的结果为0是正确的。这三个数组在查找的过程中都存在array[left] == array[right] == array[mid]的情况。