【剑指Offer 8】旋转数组的最小数字

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

Java代码如下：

package demo;

public class TestMinNum {
    /**
     * @param number 旋转数组
     * @return 数组的最小值
     */
    public static int min(int[] number) {
        // 判断输入是否合法
        if(number == null || number.length == 0) {
            throw new RuntimeException("Invalid input");
        }
        // 开始处理的第一个位置
        int low = 0;
        // 开始处理的最后一个位置
        int high = number.length - 1;
        // 设置中间位置初始值为第一个位置的值
        int middle = low;
        // 旋转数组的第1个元素不小于最后1个元素
        while(number[low] >= number[high]) {
            // 当处理范围只有2个数据时，返回后一个结果
            if(high - low == 1) {
                return number[high];
            }
            // 取中间位置
            middle = low + (high - low) / 2;
        
            // 特殊情况；如果3个数都相等，则需要进行顺序处理，从头到尾找最小值
            if(number[middle] == number[low] && number[high] == number[middle]) {
                return minInOrder(number, low, high);
            }
        
            // 如果中间位置对应的值在前1个排好序的部分，将low设置为新的位置
            if(number[middle] >= number[low]) {
                low = middle;
            } else if(number[middle] <= number[high]) {
                // 如果中间位置对应的值在后1个排好序的部分，将high设置为新的位置
                high = middle;
            }
        
        }
        // 返回最终的处理结果
        /*
         * 同时包含了特殊情况：旋转数组本身就是排序数组：number[low] < number[high]，
         * 则直接将low位置的值返回
         */
        return number[middle];
    }

    // 特殊情况；如果3个数都相等，则需要进行顺序处理，从头到尾找最小值
    private static int minInOrder(int[] number, int low, int high) {
        int min = number[low];
        for (int i = low; i < high; i++) {
            if(min > number[i]) {
                min = number[i];
            }
        }
        return min;
    }

    public static void main(String[] args) {
        // Test1. 典型输入：单调升序的数组的一个旋转
        int[] number1 = {3, 4, 5, 1, 2};
        System.out.println("Test1的结果： " + min(number1));
        // Test2. 有重复数字，并且重复数字刚好是最小的数字
        int[] number2 = {3, 4, 5, 1, 1, 2};
        System.out.println("Test2的结果： " + min(number2));
        // Test3. 最后一个数字重复
        int[] number3 = {3, 4, 5, 1, 2, 2};
        System.out.println("Test3的结果：" + min(number3));
        // Test4. 第1个数字，最后1个数字，中间数字重复
        int[] number4 = {1, 0, 1, 1, 1};
        System.out.println("Test4的结果：" + min(number4));
        // Test5. 第1个数字，最后1个数字，中间数字重复
        int[] number5 = {1, 1, 1, 0, 1};
        System.out.println("Test5的结果：" + min(number5));
        // Test6. 排序数组
        int[] number6 = {1, 2, 3, 4, 5};
        System.out.println("Test6的结果：" + min(number6));
        // Test7. 只有1个数字
        int[] number7 = {1};
        System.out.println("Test7的结果：" + min(number7));
        // Test8. 数字都相同
        int[] number8 = {1, 1, 1, 1, 1};
        System.out.println("Test8的结果：" + min(number8));
        // Test9. 输入为null
        // System.out.println("Test9的结果：" + min(null));
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/45457859