🌕 153. 寻找旋转排序数组中的最小值

难度: 🌕

问题描述

---

解法

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

    private int mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return nums[left];
        }
        if(left == right - 1) {
            return Math.min(nums[left], nums[right]);
        }
        // 节点数必 >= 3 => mid 必 != left
        int mid = left + ((right - left) >> 1);
        // 找旋转点
        if(nums[mid] > nums[mid + 1]) {
            // mid 正好是旋转点前最大值
            return nums[mid + 1];
        }
        if(nums[mid] < nums[right]) {
            // 右侧必定单增
            // 反证：若 mid 右侧有旋转点，那么 [right] 必 < [left]，
            // 而只有一个旋转点，说明左侧必定有序，那么 [mid] 必 >= [left] > [right] 与 [mid] < [right] 矛盾
            return mySol(nums, left, mid);
        }
        if(nums[mid] > nums[left]) {
            return mySol(nums, mid + 1, right);
        }
        return -1;
    }
}

---

输出