佛山专业做网站公司,wordpress调用文章内容标签,wordpress汽车主题,国内跨境电商平台排行榜前十名题目#xff1a;33. 搜索旋转排序数组
思路#xff1a;看到时间复杂度要求是O(log N)很容易想到二分查找#xff0c;普通的二分查找我们已经掌握#xff0c;本题中的数组可以看作由两个分别升序的数组拼成#xff0c;在完全升序的部分中进行二分查找是容易的#xff0c;…题目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(vectorint nums, int target) {int lennums.size();int l0,rlen-1;while(lr){int mid (lr)/2;if(targetnums[mid]) return mid;if(nums[l]nums[mid]){if(targetnums[l]targetnums[mid]) rmid-1;else lmid1;}else if(targetnums[mid]targetnums[r]) l1mid;else rmid-1; }return -1;}
};
补充
在二分法中左右指针的移动和循环条件的细微改变都会引起结果的不同。比如循环条件是while(lr) 还是 while(lr)指针移动方式是lmid还是lmid1。我没有深入研究原理只是观察并且猜测whilelr)与lmid1搭配使用是其中一种正确的方式也许可以死板地记忆以下。
