题目
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)的复杂度，要利用排序的信息的话要求应该是O(log(n))。所以首先排除通过线性扫描找到最大值确定头尾的方法。
但是如果不知道最大值，我真的是不知道怎么操作，所以考虑用O(log(n))的方法寻找最大值的位置。
由于最大值左侧的数一定比最大值右侧的数大（如果最大值在中间的话），可以这点逐步缩小搜索空间。
在区间[a, b]中，取其中点c，则有以下情况：
- a<=b：b为最大值（已经假设没有重复元素，但如果a,b为同一元素则需要返回）
- a>b且a>=c：最大值在(a, c)之间（使用等于号是考虑到a,c为同一元素的情况）
- a>b且a<c：最大值在(c, b)之间
找到最大值后使用二分法即可完成查找。
实现
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);
}
};
思考
做得有点慢，关于stl的这些东西还是要熟练啊。
中间因为没用小于等于改了好多次，边界情况开始要注意啊。
另外看所用时间，感觉不用递归以及stl会快一点=_=
