題目
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.
分析
直接搜索是O(n)的復(fù)雜度，要利用排序的信息的話要求應(yīng)該是O(log(n))。所以首先排除通過線性掃描找到最大值確定頭尾的方法询吴。
但是如果不知道最大值宦芦，我真的是不知道怎么操作卵皂，所以考慮用O(log(n))的方法尋找最大值的位置童本。
由于最大值左側(cè)的數(shù)一定比最大值右側(cè)的數(shù)大（如果最大值在中間的話），可以這點(diǎn)逐步縮小搜索空間。
在區(qū)間[a, b]中婿脸，取其中點(diǎn)c，則有以下情況：
- a<=b：b為最大值（已經(jīng)假設(shè)沒有重復(fù)元素似枕，但如果a,b為同一元素則需要返回）
- a>b且a>=c：最大值在(a, c)之間（使用等于號(hào)是考慮到a,c為同一元素的情況）
- a>b且a<c：最大值在(c, b)之間
找到最大值后使用二分法即可完成查找盖淡。
實(shí)現(xiàn)
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0) return -1;
int idxmax = binary_max(nums, 0, nums.size()-1);
if(target>=nums[0]){
auto itu = lower_bound(nums.begin(), nums.begin()+idxmax+1, target);
if(itu==nums.begin()+idxmax+1 || *itu!=target) return -1;
return itu - nums.begin();
}
else{
auto itv = lower_bound(nums.begin()+idxmax+1, nums.end(), target);
if(itv==nums.end() || *itv!=target) return -1;
return itv - nums.begin();
}
}
private:
int binary_max(vector<int>& nums, int start, int end){
if(nums[start]<=nums[end])
return end;
int mid = (start + end) / 2;
if(nums[start]>=nums[mid])
return binary_max(nums, start, mid);
else
return binary_max(nums, mid, end);
}
};
思考
做得有點(diǎn)慢，關(guān)于stl的這些東西還是要熟練啊凿歼。
中間因?yàn)闆]用小于等于改了好多次褪迟，邊界情況開始要注意啊。
另外看所用時(shí)間答憔，感覺不用遞歸以及stl會(huì)快一點(diǎn)=_=
