搜索旋转排序数组

没思路。

看了下全网的思路,一个个来o，多做点题就知道了二分不仅仅只能用在有序的数组中。

这道题很关键的一个值就是nums[0]。

法一：先用二分找到旋转点，旋转点两边都是的，判断要搜索的值在哪边，对那边再二分找值就可以了。

怎么判断要搜索的值在哪边呢，还是通过与nums[0]做对比就可以了。

代码：

class Solution {
public:int search(vector<int>& nums, int target) {int l=0,r=nums.size()-1;while(l<r){int mid = (l+r+1)>>1;if(nums[0]>nums[mid]) r=mid-1;else l=mid;}//此时，l和r是最大值if(target>=nums[0]) //这种情况在前半部分进行二分{l=0;}else{r=nums.size()-1;l=l+1;} while(l<r){int mid=l+r+1>>1;if(nums[mid]>target) r=mid-1;else l=mid;}if(nums[r]==target)  return r;return -1;}
};

法二：直接取mid，一定分为顺序区间和一个乱序区间。

这种方法使用了二分查找的思想，在每次迭代中，都会根据数组的局部有序性来缩小搜索范围：

• 先通过中间位置判断目标值是否已经找到。
• 然后根据数组的有序区间，判断目标值是位于左半部分还是右半部分，并且调整边界继续搜索。
• 这种方法的时间复杂d度是 O(log n)，因此在大数组中搜索目标值非常高效。

代码：

class Solution {
public:int search(vector<int>& nums, int target) {int l=0,r=nums.size()-1;while(l<=r){int mid=(l+r)>>1;if(nums[mid]==target) return mid;if(nums[l]<=nums[mid])//一边无序则另一边必有序{if(nums[mid]>target&&target>=nums[l]) r=mid-1;else l=mid+1;}else{if(nums[r]>=target&&target>nums[mid]) l=mid+1;else r=mid-1;}} return -1;}
};