「力扣」第 153 题、第 154 题：分治算法的解法

• 本题是「力扣」第 153 题：寻找旋转排序数组中的最小值；
• 本题最常见的解法还是「二分查找」，可以见 题解；
• 「分治思想」的解法：把待搜索的区间一分为二，然后根据 nums[mid] 和 nums[right] 的值，决定接下来在哪个区间里继续查找；
• 「分治思想」的解法其实就是把「二分查找」写成「递归」的形式。

参考代码：

public class Solution {

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

    private int findMin(int[] nums, int left, int right) {
        if (nums[left] == nums[right]) {
            return nums[left];
        }

        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) {
            return findMin(nums, mid + 1, right);
        } else {
            return findMin(nums, left, mid);
        }
    }
}

• 本题是「力扣」第 154 题：寻找旋转排序数组中的最小值 II；
• 本题最常见的解法还是「二分查找」，可以见 题解；
• 「分治思想」的解法：把待搜索的区间一分为二，然后根据 nums[mid] 和 nums[right] 的值，决定接下来在哪个区间里继续查找；
• 「分治思想」的解法其实就是把「二分查找」写成「递归」的形式。

参考代码：

public class Solution {

    public int findMin(int[] nums) {
        // 在 nums[left..right] 里查找目标元素
        return findMin(nums, 0, nums.length - 1);
    }

    private int findMin(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left + right) / 2;
        if (nums[mid] == nums[right]) {
            return findMin(nums, left, right - 1);
        } else if (nums[mid] < nums[right]) {
            // 下一轮搜索区间是 [left..mid]
            return findMin(nums, left, mid);
        } else {
            // 下一轮搜索区间是 [mid + 1..right]
            return findMin(nums, mid + 1, right);
        }
    }
}