33. 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
解题思路：
（此解题思路参考 Code Ganker[1]，不同之处在于，对原有解题思路加入自己的理解做进一步阐述）
将nums数组元素与target进行比较时候，考虑3种情况：
⑴当nums[d]=target时，程序结束，找到target位置
⑵当nums[d]!=target时，
①当中间值（位置为d）小于右边缘（位置为r）时，表明数组nums中[d,r]区间内是有序的，于是这里只需判断target是否落在[d,r]区间即可判定，target的位置，这里有个问题，如果target落在[l,r]区间，此区间无序，是否说明，仅仅只对[d,r]区间进行二分查找得出target的位置这里论断是错误的呢？不是，当在有序序列中进行判定target时候，我们加了限制条件，比如[d,r]区间有序，那个我们对左边缘是否右移的判定条件是nums[r]>=target && target>nums[m]，并且不满足合格条件，搜索区间会慢慢向无序区间偏移，这里就可以打消我们的顾虑了，虽然起初我们只对有序区间进行判断，但是当我们在有序区间找不到target时，搜索区间会自动向无序区间挤压，这里也就相当于最终所有区间都搜索到了…
#include <iostream>
#include <vector>
using namespace std;
int search(vector<int>& nums, int target)
{
if(nums.size()==0) return -1;
int l=0,r=nums.size()-1;
while(l<=r){
int m=(l+r)/2;
if(target==nums[m]) return m;
if(nums[m]<nums[r]){
if(nums[r]>=target && target>nums[m]) l=m+1;
else r=m-1;
}else{
if(nums[l]<=target && target<nums[m]) r=m-1;
else l=m+1;
}
}
return -1;
}
int main(){
vector<int>v={0,1,2,4,5,6,7};
int t=5;
cout<<search(v,t);
}
