题解 | 旋转数组的最小数字

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return minNumberInRotateArray(nums, 0, nums.length - 1);
    }


    static public int minNumberInRotateArray(int[] nums, int low, int high) {
        if (low >= high) {
            return nums[low];
        }
        int mid = (low + high) / 2;

        //查找开始节点和中间节点和最后节点的最大值
        int max = Math.max(nums[mid], Math.max(nums[high], nums[low]));
        //中间最大
        if (nums[mid] == max) {
            //头等于尾
            if (nums[low] == nums[high]) {
                return Math.min(minNumberInRotateArray(nums, mid + 1, high),
                                minNumberInRotateArray(nums, low, mid));
            }
            if (nums[low] < nums[high]) {
                return  minNumberInRotateArray(nums, low, mid);
            } else {
                //最小的一定在最后
                return minNumberInRotateArray(nums, mid + 1, high);
            }
            //开始最大
        } else if (nums[low] == max) {
            //需要比较中间和结尾的大小
            //中间大，说明在右边
            if (nums[mid] > nums[high]) {
                return  minNumberInRotateArray(nums, mid + 1, high);
            } else {
                //中间小，在左边
                return  minNumberInRotateArray(nums, low, mid);
            }
            //最后的最大
        } else {
            return nums[low];
        }

    }
}