33. Search in Rotated Sorted Array
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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Subscribe to see which companies asked this question.
My Thought
题目的大致意思是，给定一个升序数组，但是这个数组在某个位置进行了旋转，比如上述题目中的例子。然后给定一个数字，让你找出该数字在数组中的位置。
一般的二分搜索肯定是不行了。
对于一个未旋转的升序数组：
$$x_1\leq x_2\leq x_3...\leq x_n\]
假定旋转元素是\(x_j\),则旋转后
\]
其中左半部分恒有\(\geq x_j\),同理，右半部分\(\leq x_j\),对于二分查找，每次 mid 的落点不是在右半部分，就是在左半部分。
问题具有对称性，我们假设落点在左半部分，即
\]
那么当目标元素 target 落在 \([j+1,mid]\) 之间时，就是一个普通的二分查找问题，return binary_search(j+1,mid) 即可，如果 target 落在\([mid,n]\)之间，那么问题变成了原问题的子问题,此时查找区间变成了
\]
最后注意一下查找不到的情况，和递归结束条件即可。
Code(C++ 9ms)
class Solution {
public:
int bs(vector<int>&nums, int l,int h, int t){
if(l<=h){
int mid = (l+h)/2;
if(nums[mid]<t)
return bs(nums,mid+1,h,t);
else if(nums[mid]>t)
return bs(nums,l,mid-1,t);
return mid;
}
return -1;
}
int rsearch(vector<int>&nums, int l,int h, int target){
if(l<=h){
int mid = (l+h) / 2;
if(nums[mid]==target)
return mid;
// big part
if(nums[mid]>=nums[l]){
if(target>=nums[l]&&target<=nums[mid])
return bs(nums,l,mid,target);
else
return rsearch(nums,mid+1,h,target);
}
// small part
else if(nums[mid]<nums[l]){
if(target<=nums[h]&&target>=nums[mid])
return bs(nums,mid,h,target);
else
return rsearch(nums,l,mid-1,target);
}
}
return -1;
}
int search(vector<int>& nums, int target) {
if(nums.size()<1)
return -1;
return rsearch(nums, 0, nums.size()-1,target);
}
};
另外最近闲着没事就会去leetcode刷题（keep coding 233），题解都放在了我的上github-LeetCodeSolution上，有兴趣的可以star一下啊（各位父老乡亲帮帮忙TT。P.S.题解都是用markdown写的，而且有时候还会用尴尬的英语。。另外github好像不支持LaTeX公式，需要的可以用自己的markdown编辑器打开。