LeetCode 33 Search in Rotated Sorted Array [binary search] <c++>
给出排序好的一维无重复元素的数组，随机取一个位置断开，把前半部分接到后半部分后面，得到一个新数组，在新数组中查找给定数的下标，如果没有，返回-1。时间复杂度限制\(O(log_2n)\)
C++
我的想法是先找到数组中最大值的位置。然后以此位置将数组一分为二，然后在左右两部分分别寻找target。
二分寻找最大值的时候，因为左半部分的数一定大于nums[l],所以nums[mid]和nums[l]比较大小就可以知道最大值的位置在mid的左侧还是右侧。
在两个单调区间分别二分查找target时，可以直接使用STL提供的lower_bound函数
class Solution {
public:
int search(std::vector<int>& nums, int target) {
if(nums.empty()) return -1;
int l = 0,r = nums.size();
while(l!=r){
int mid = (l+r)/2;
if(nums[mid]>nums[l]) l = mid;
else r = mid;
}
auto iter = std::lower_bound(nums.begin(),nums.begin()+l+1,target);
if(*iter == target && std::distance(nums.begin(),iter)<=l) return std::distance(nums.begin(),iter);
iter = std::lower_bound(nums.begin()+l+1,nums.end(),target);
if(*iter == target && std::distance(nums.begin(),iter)<nums.size()) return std::distance(nums.begin(),iter);
return -1;
}
};
然鹅标程只用了一次二分就搞定了...
学习改进后：
class Solution {
public:
int search(std::vector<int>& nums, int target) {
int l = 0,r = nums.size();
while (l<r){
const int mid = l + (r-l)/2;
if(nums[mid] == target) return mid;
if(nums[l] <= nums[mid])
if(nums[l] <= target && target < nums[mid]) r = mid;
else l = mid + 1;
else
if(nums[mid] < target && target <= nums[r-1]) l = mid + 1;
else r = mid;
}
return -1;
}
};