网站的逻辑结构免费咨询心理医生qq号

题目：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搭配使用是其中一种正确的方式，也许可以死板地记忆以下。