AC 剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1
示例 2：

输入：[2,2,2,0,1]
输出：0

class Solution {
    /**
     * @Title: minArray
     * @Description: 二分查找
     * @author: itbird
     * @date 2022年3月15日 下午7:45:43
     * @param numbers
     * @return int 时间复杂度: O(logn) 空间复杂度: O(1)
     */
    public int minArray(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return -1;
        }

        // 使用二分查找
        int min = binarySearch(0, numbers.length - 1, numbers);
        return min;
    }

    private int binarySearch(int left, int right, int[] numbers) {
        // 此处使用二分查找，最大的难点，在于数组现在是分为两个有序数组，所以针对于不同的情况，我们需要做处理

        while (left < right) {
            int mid = (left + right) / 2;
            if (numbers[right] > numbers[mid]) {
                // 如果右边大于中间，说明最小值在中间的左端，我们此时舍弃右半部分
                right = mid;
            } else if (numbers[right] < numbers[mid]) {
                // 如果右边小于中间，说明最小值在中间的右端，我们此时舍弃左半部分
                left = mid + 1;
            } else {
                // 如果右边的值等于中间的值，此时我们由于重复元素的存在，我们不能舍弃左右
                right--;
            }
        }
        return numbers[left];
    }

    /**
     * @Title: minArray
     * @Description: 暴力查找
     * @author: itbird
     * @date 2022年3月15日 下午7:45:43
     * @param numbers
     * @return int 时间复杂度: O(N) 空间复杂度: O(1)
     */
    public int minArray1(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return -1;
        }

        int min = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < min) {
                min = numbers[i];
            }
        }
        return min;
    }
}