博文中会简要介绍Leetcode P0153题目分析及解题思路。
“Find Minimum in Rotated Sorted Array”这道题是p0033的变形题，在p0033中我们要寻找特定的target，这里特定的target是整个数组中的最小值，虽然我们无法得知最小值，但是我们依旧可以通过考虑mid和数组两端（或者mid两边邻居）的关系来判断最小值在左半边还是右半边区间，从而二分搜索。
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
以下是Java的题解代码实现。
class Solution {
public int findMin(int[] nums) {
int N = nums.length;
int left = 0, right = N-1, mid = 0;
while (left <= right) {
mid = (left+right)/2;
int leftNum = (mid > 0)? nums[mid-1]: Integer.MAX_VALUE;
int rightNum = (mid < N-1)? nums[mid+1]: Integer.MAX_VALUE;
// 恰好是最小值
if (nums[mid] < leftNum && nums[mid] < rightNum) {
return nums[mid];
}
// 如果当前这个点大于左右两端，说明最小值在其右边
else if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
left = mid+1;
}
// 如果当前这个点小于左右两端，说明最小值在其左边
// 或者当前[left,right]区间恰好是个递增序列，那么最小值在左端
else {
right = mid-1;
}
}
return nums[mid];
}
}
上述代码实现是用迭代的思路。这道题也可以使用递归的思路。递归思路上可以与迭代一致，也可以有些微不同，比如说上述做法是关注mid和两端的关系，其实也可以直接考虑mid和其左边邻接值的关系。
以下是Java的题解代码实现。
class Solution {
public int findMin(int[] nums) {
if (nums[nums.length-1] > nums[0]) {
return nums[0];
}
return this.binarySearch(nums, 0, nums.length-1);
}
private int binarySearch(int[] nums, int start, int end) {
// Only less than or equal to 2 numbers are left
if (end-start <= 1) {
return Math.min(nums[start], nums[end]);
}
int mid = (start+end)/2;
// if n[mid-1] < n[mid] < n[mid+1]
if (nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1]) {
// if n[mid] > n[0], then search right part
if (nums[mid] > nums[0]) {
return this.binarySearch(nums, mid+1, end);
}
else {
return this.binarySearch(nums, start, mid-1);
}
}
// if n[mid-1] < n[mid] > n[mid+1]
else if (nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]) {
return nums[mid+1];
}
// if n[mid-1] > n[mid] < n[mid+1]
else {
return nums[mid];
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
int findMin(vector<int>& nums) {
int N = nums.size();
int left = 0, right = N-1, mid = 0;
while (left <= right) {
mid = (left+right)/2;
int left_num = (mid > 0)? nums[mid-1]: INT_MAX;
int right_num = (mid < N-1)? nums[mid+1]: INT_MAX;
// 恰好是最小值
if (nums[mid] < left_num && nums[mid] < right_num) {
return nums[mid];
}
// 如果当前这个点大于左右两端，说明最小值在其右边
else if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
left = mid+1;
}
// 如果当前这个点小于左右两端，说明最小值在其左边
// 或者当前[left,right]区间恰好是个递增序列，那么最小值在左端
else {
right = mid-1;
}
}
return nums[mid];
}
};