假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。

你可以假设数组中不存在重复的元素。

 

样例

给出[4, 5, 1, 2, 3]和target=1，返回 2

给出[4, 5, 1, 2, 3]和target=0，返回 -1

 

 

还是二分法，关键就是想明白二分之后怎么办，前半和后半有什么关系，有哪些情况？

分一半之后三种情况

1、正好中间就是target，找到了

2、前半是排好序的，A[mid]>=A[left]，如果target在这个范围，二分继续查下去就行了

3、后半是排好序的，A[mid]<A[left]，同上

所以重点还是从无序中找出有序，有序中找就成了常规的二分问题

1 int search(vector
      
        &A, int target) { 2         // write your code here 3         int left=0,right=A.size()-1; 4         int mid; 5         while(left<=right){ 6             mid=(right+left)/2; 7             if(target==A[mid]){ 8                 return mid; 9             }10             if(A[mid]>=A[left]){11                 if(A[left] <= target && target < A[mid]) {12                     right = mid - 1;13                 }14                 else{15                     left = mid + 1;16                 }17             }18             else{19                 if(A[mid] < target && target <= A[right])  {20                     left = mid + 1;21                 }22                 else  {23                     right = mid - 1;24                 }25             }26         }27         return -1;28     }