- 本题是「力扣」第 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);
}
}
}
