一、 題目
在一個數組中查詢一個目標數，給出的是一個有序的數組、元素個數和目標數，不過特別的是這個數組可能是旋轉(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]
（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[mid]&&target<=A[right])
left = mid+1;
else
right = mid -1;
}
else if(target>=A[left]&&target
