要求
給定一沒有重復元素的旋轉數組（它對應的原數組是有序的），求給定元素在旋轉數組內的下標（不存在的返回-1）。
例如
有序數組為{0,1,2,4,5,6,7},它的一個旋轉數組為{4,5,6,7,0,1,2}.
元素6在旋轉數組內，返回2
元素3不在旋轉數組內，返回-1
分析托福答案
遍歷一遍，可以輕松搞定，時間復雜度為O（n），因為是有序數組旋轉得到，這樣做肯定不是最優解。有序，本能反映用二分查找，舉個例子看看特點
可以看出中間位置兩段起碼有一個是有序的（不是左邊，就是右邊），那么就可以在有序的范圍內使用二分查找；如果不再有序范圍內，就到另一半去找。
參考代碼
復制代碼
int search（int A[], int n, int target） {
int beg = 0;
int end = n - 1;
while （beg <= end）
{
int mid = beg + （end - beg） / 2;
if（A[mid] == target）
return mid;
if（A[beg] <= A[mid]）
{
if（A[beg] <= target && target < A[mid]）
end = mid - 1;
else
beg = mid + 1;
}
else
{
if（A[mid] < target && target <= A[end]）
beg = mid + 1;
else
end = mid - 1;
}
}
return -1;
}
復制代碼
擴展
上邊的有求是沒有重復的元素，現在稍微擴展下，可以有重復的元素，其他的要求不變。
思路雅思答案
大致思路與原來相同，這是需要比較A[beg] 與 A[mid]的關系
A[beg] < A[mid] ----左邊有序
A[beg] > A[mid] ----右邊有序
A[beg] = A[mid] ----++beg
復制代碼
bool search（int A[], int n, int target） {
int beg = 0;
int end = n - 1;
while （beg <= end）
{
int mid = beg + （end - beg） / 2;
if（A[mid] == target）
return true;
if（A[beg] < A[mid]）
{
if（A[beg] <= target && target < A[mid]）
end = mid - 1;
else
beg = mid + 1;
}
else if（A[beg] > A[mid]）
{
if（A[mid] < target && target <= A[end]）
beg = mid + 1;
else
end = mid - 1;
}
else
++beg;
}
return false;
}