从零开始的LC刷题(124): Search in Rotated Sorted Array 位移后的已排序数列中的二分查找

原题：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

题意是已排序的数列发生位移，比如1234567 =》3456712，然后要求在Ologn时间里进行查找，那就是二分查找了，我的方法是先二分找到pivot位移量，再根据位移进行二分查找，结果：

Success

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Search in Rotated Sorted Array.

Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Search in Rotated Sorted Array.

代码：

class Solution { public: int search(vector<int>& nums, int target) { if(!nums.size()){return -1;} if(nums.size()==1){if(nums[0]==target){return 0;};return -1;} int l=0; int r=nums.size(); while(l<r-1){ int m=(l+r)/2; if(nums[m]>nums[l]){ l=m; } else r=m; } int size=nums.size(); int pivot=(l+1)%size; l=0;r=size-1; int m=-1; while(l<=r){ m=(l+r)/2; if(nums[(m+pivot)%size]==target){return (m+pivot)%size;} else if(nums[(m+pivot)%size]<target){l=m+1;} else r=m-1; //cout<<l<<r;; } return -1; } };