题解 | #旋转数组的最小数字#减治思想已秒杀

默认你已经理解题意

思路如下

二分查找来解（减治思想）

题目中给出的数组是一半有序，虽然咱们知道传统二分告诉我们二分只能用在有序数组上面，但事实上，只要是可以减治的问题，仍然可以用二分思想。

说下流程哈

数组中最特殊的位置是左边位置 left 和右边位置 right，然后把它们与中间位置 mid 的值进行比较，从而判断最小数字出现的位置在哪里。

那左边位置 left 的值和中间位置 mid 的值可以进行比较吗？

比如说：[3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5] 这两个数组，此时，中间位置的值都比左边大，但最小值一个在后面，一个在前面，那么这种做法不能有效地减治的哦。

用右边位置 right 和中间位置 mid 的值进行比较是否可以？

比如说：[1, 2, 3, 4, 5]、[3, 4, 5, 1, 2]、[2, 3, 4, 5 ,1]这两个数组，用右边位置和中间位置的元素进行比，可以进一步缩小搜索的范围。

强调的是如果遇到 nums[mid] == nums[right] 的时候，不能草率地下定结论最小数字在哪一边，但是肯定的是，把 right 舍弃掉，并没有影响结果的哈。

public class Solution {

    // [3, 4, 5, 1, 2]
    // [1, 2, 3, 4, 5]
    // 不能使用左边数与中间数比较，这种做法不能有效地减治

    // [1, 2, 3, 4, 5]
    // [3, 4, 5, 1, 2]
    // [2, 3, 4, 5 ,1]

    public int minArray(int[] numbers) {
        int len = numbers.length;
        if (len == 0) {
            return 0;
        }
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (numbers[mid] > numbers[right]) {
                // [3, 4, 5, 1, 2]，mid 以及 mid 的左边一定不是最小数字
                // 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else if (numbers[mid] == numbers[right]) {
                // 只能把 right 排除掉，下一轮搜索区间是 [left, right - 1]
                right = right - 1;
            } else {
                // 此时 numbers[mid] < numbers[right]
                // mid 的右边一定不是最小数字，mid 有可能是，下一轮搜索区间是 [left, mid]
                right = mid;
            }
        }

        // 最小数字一定在数组中，因此不用后处理
        return numbers[left];
    }
}

分治法来解

我写分治的时候，还是写成了二分。因为二分的减治思想其实本来就是分治思想的特殊情况,下面代码不难看下

//Java的代码
public class Solution {

    public int minArray(int[] nums) {
        int len = nums.length;
        return minArray(nums, 0, len - 1);
    }

    private int minArray(int[] nums, int left, int right) {
        if (left + 1 >= right) {
            return Math.min(nums[left], nums[right]);
        }

        if (nums[left] < nums[right]) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return Math.min(minArray(nums, left, mid - 1), minArray(nums, mid, right));
    }
}