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

难度: 🌕🌗

问题描述

---

解法

class Solution {
    public int minArray(int[] numbers) {
        // 思路：
        // 二分
        int len = numbers.length;
        return mySol(numbers, 0, len - 1);
    }

    private int mySol(int[] numbers, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return numbers[left];
        }
        if(left == right - 1) {
            return Math.min(numbers[left], numbers[right]);
        }
        // 至少 3 个元素
        int mid = left + ((right - left) >> 1);
        if(numbers[mid] > numbers[left]) {
            // 左半区间升序
            if(numbers[right] <= numbers[left]) {
                // 在右半区间
                return mySol(numbers, mid, right);
            } else {
                return numbers[left];
            }
        } else if(numbers[mid] == numbers[left]) {
            // 左移一个单位
            return mySol(numbers, left + 1, right);
        } else {
            // [mid] < [left]
            return mySol(numbers, left, mid);
        }
    }
}

---

输出