博文中会简要介绍Leetcode P0033题目分析及解题思路。
“Search in Rotated Sorted Array”是一道二分查找的变形题。主要考察对指针移动的边界条件的判断。
Given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums 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]).
You should search for target in nums and if you found return its index, otherwise return -1.
由于排好序的数组被“旋转”了，mid指针落在的位置就会出现不同情况，一种是落在左半边升序序列，一种是落在右半边升序序列，还有一种是在移动left和right指针后，left和right指针组成了一个单调升序序列，mid指针恰好落在了这个升序序列上。
以下是Java的题解代码实现。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while (left <= right) {
int mid = (left+right)/2;
if (nums[mid] == target)
return mid;
// 落在升序序列上，按普通的二分查找移动left和right即可
if (nums[mid] >= nums[left] && nums[mid] <= nums[right]) {
if (target > nums[mid])
left = mid+1;
else
right = mid-1;
}
// 落在左半边升序序列
else if (nums[mid] >= nums[left] && nums[mid] >= nums[right]) {
// target在mid指针左边的升序序列上
if (target >= nums[left] && target < nums[mid])
right = mid-1;
else
left = mid+1;
}
// 落在右半边升序序列
else if (nums[mid] <= nums[left] && nums[mid] <= nums[right]) {
// target在mid指针右边的升序序列上
if (target > nums[mid] && target <= nums[right])
left = mid+1;
else
right = mid-1;
}
}
return -1;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid = (left+right)/2;
if (nums[mid] == target)
return mid;
if (nums[mid] >= nums[left] && nums[mid] <= nums[right]) {
if (target > nums[mid])
left = mid+1;
else
right = mid-1;
}
else if (nums[mid] >= nums[left] && nums[mid] >= nums[right]) {
if (target >= nums[left] && target < nums[mid])
right = mid-1;
else
left = mid+1;
}
else if (nums[mid] <= nums[left] && nums[mid] <= nums[right]) {
if (target > nums[mid] && target <= nums[right])
left = mid+1;
else
right = mid-1;
}
}
return -1;
}
};