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.
题目翻译
给定一个升序排列的数组，它在某一个你事先不知道的位置发生颠换。 例如： 0 1 2 3 4 5 6 7 变成 4 5 6 7 0 1 2 给出一个值让你在这个数组中搜索。如果找到则返回这个值在数组的索引，否则返回-1。 你可以假设在这个数组中不存在重复。
解题方案
标签： Binary Search
思路：
- 题目要求我们用二分查找法来搜索目标数值在数组的位置。
- 因为rotate的缘故，当我们切取一半的时候可能会出现误区，所以我们要做进一步的判断。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
- 如果target==A[m]，那么m就是我们要的结果，直接返回；
- 如果A[m] < A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1；
- 如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size()==0)
return -1;
int l=0;
int r=nums.size()-1;
while(l<=r){
int m=(l+r)/2;
if(nums[m]==target)
return m;
else if(nums[m]<nums[r]){
if(target>nums[m]&&target<=nums[r])
l=m+1;
else
r=m-1;
}
else{
if(target>=nums[l]&&target<nums[m])
r=m-1;
else
l=m+1;
}
}
return -1;
}
};