一、 题目
在一个数组中查询一个目标数，给出的是一个有序的数组、元素个数和目标数，不过特别的是这个数组可能是旋转(rotate)的。
例如：数组可能是 0、1、2、4、5、6
也可能是4、5、6、0、1、2
二、 分析
这个题首先我们会想到二分查找，但是仔细想想好像又不是，因为不一定是正序的，还有可能旋转，因为rotate的原因，如果我们取一半的时候可能会出现错误，二分法不是不行，难度在于左右边界的确定，所以我们要做进一步的判断数的精确位置。假设数组是A，每次左边缘为left，右边缘为right，还有中间位置是mid。
分三种情况：
（1）如果target==A[mid]，那么mid就是我们要的结果，直接返回；
（2）如果A[mid]<A[right]，那么说明从mid到right一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在mid到right之间，如果是则把左边缘移到mid+1，否则就target在另一半，即把右边缘移到mid-1。
（3）如果A[mid]>=A[right]，那么同样说明从left到mid一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
class Solution {
public:
int search(int A[], int n, int target) {
if(n==0)
return -1;
int left = 0;
int right = n-1;
int mid;
while(left <= right) {
mid = (left+right)/2;
if(target==A[mid])
return mid;
//确定数组特征
if(A[mid]<A[right]){
if(target>A[mid]&&target<=A[right])
left = mid+1;
else
right = mid -1;
}
else if(target>=A[left]&&target<A[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
};