剑指Offer面试题：9.旋转数组的最小数字

一、题目
————————————————
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
————————————————
二、思路
————————————————
　　数组在一定程度上是排序的，很容易分析出：可以采用二分法来寻找最小数字。
　　但是这里面有一些陷阱：
　　1.递增排序数组的本身是自己的旋转，则最小数字是第一个数字
　　2.中间数字与首尾数字大小相等，如{1,0,1,1,1,1}和{1,1,1,1,0,1}，无法采用二分法，只能顺序查找。
————————————————
三、解决问题
————————————————
测试用例
　　1.功能测试（正常旋转数组，中间有或者无重复数字）
　　2.边界值测试（升序数组，1个数字的数组）
　　3.特殊输入测试（null，空数组）
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-14 10:12
 */

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

 */

public class Solution09 {

    public static void main(String[] args) {
        System.out.println("==============================");
        Solution09 sword = new Solution09();
        sword.test1();
        System.out.println("==============================");
        sword.test2();
        System.out.println("==============================");
        sword.test3();
        System.out.println("==============================");
        sword.test4();
        System.out.println("==============================");
        sword.test5();
        System.out.println("==============================");
        sword.test6();
        System.out.println("==============================");
        sword.test7();
        System.out.println("==============================");
    }

    /**
     * 数组在一定程度上是排序的，很容易分析出：可以采用二分法来寻找最小数字。
     　　但是这里面有一些陷阱：
     　　1.递增排序数组的本身是自己的旋转，则最小数字是第一个数字
     　　2.中间数字与首尾数字大小相等，如{1,0,1,1,1,1}和{1,1,1,1,0,1}
           无法采用二分法，只能顺序查找。
     * @param array
     * @return
     */
    public int minNumberInRotateArray(int [] array) {
        //空数组或者null时返回0
        if (null == array || array.length <= 0) {
            return 0;
        }
        int low = 0;
        int high = array.length - 1;
        //正常情况
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (array[mid] > array[high]) {
                low = mid + 1;
            } else if (array[mid] == array[high]) {
                high = high - 1;
            } else {
                high = mid;
            }
        }
        return array[low];
    }
    // =======测试代码======
    public void test1() {
        int[] array = null;
        System.out.println("test1:" + minNumberInRotateArray(array));
    }

    public void test2() {
        int[] array = {};
        System.out.println("test2:" + minNumberInRotateArray(array));
    }

    public void test3() {
        int[] array = { 1 };
        System.out.println("test3:" + minNumberInRotateArray(array));
    }

    public void test4() {
        int[] array = { 1, 2, 3, 4, 5, 6 };
        System.out.println("test4:" + minNumberInRotateArray(array));
    }

    public void test5() {
        int[] array = { 2, 2, 2, 2, 1, 2 };
        System.out.println("test5:" + minNumberInRotateArray(array));
    }

    public void test6() {
        int[] array = { 2, 1, 2, 2, 2, 2 };
        System.out.println("test6:" + minNumberInRotateArray(array));
    }

    public void test7() {
        int[] array = { 6, 6, 8, 9, 10, 1, 2, 2, 3, 3, 4, 5, 6 };
        System.out.println("test7:" + minNumberInRotateArray(array));
    }
}

————————————————
　注意这段代码的一些细节：
　　1.使用low=mid+1，而不是low=mid，最终会使得low=high（即最小值位置）而跳出循环；
　　2.使用high=mid，而不是high=mid-1，因为有可能mid就是最小值点，不能减1；
　　3.升序数组的情况可以直接在循环中一起搞定，不用单独列出来判断（自己的代码还可以改进）
　　小瑕疵：
　　1.该程序在array[mid] = array[high]时直接顺序查找。但其实这还有可能可以用二分法的，除非还满足array[mid] = array[low]，才只能使用顺序查找。所以可以先排除掉必须顺序查找的情况（类似自己上面的程序，提前判断掉），之后就可以直接删除else if(array[mid] == array[high]){high = high - 1;这两行了。
　　2.缺少null的判断。
————————————————

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。