计算机低能儿从0刷leetcode | 33.搜索旋转排列数组
题目:33. 搜索旋转排序数组
思路:看到时间复杂度要求是O(log N)很容易想到二分查找,普通的二分查找我们已经掌握,本题中的数组可以看作由两个分别升序的数组拼成,在完全升序的部分中进行二分查找是容易的,因此我们每次找到mid后,判断mid左侧为完全升序还是右侧为完全升序,比如,若mid左侧为完全升序,此时如果target的范围在这当中(即nums[i]-nums[mid]中),那么就去左边寻找,否则都去右边。
因此,主要思路为以下几部分:
1、判断哪一侧是完全升序的。nums[l]<nums[mid]则左侧完全升序、否则是右侧。
2、若左侧有序且target在这个范围中,就去左边寻找,否则去右边。
3、若右侧有序且target在这个范围中,就去右边寻找,否则去左边。
4、若找不到则返回-1.
代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int len=nums.size();
int l=0,r=len-1;
while(l<=r){
int mid = (l+r)/2;
if(target==nums[mid]) return mid;
if(nums[l]<=nums[mid]){
if(target>=nums[l]&&target<nums[mid]) r=mid-1;
else l=mid+1;
}
else if(target>nums[mid]&&target<=nums[r]) l=1+mid;
else r=mid-1;
}
return -1;
}
};
补充:
在二分法中,左右指针的移动和循环条件的细微改变都会引起结果的不同。比如循环条件是while(l<r) 还是 while(l<=r),指针移动方式是l=mid,还是l=mid+1。我没有深入研究原理,只是观察并且猜测while(l<=r)与l=mid+1搭配使用是其中一种正确的方式,也许可以死板地记忆以下。