要求
給定一沒(méi)有重復(fù)元素的旋轉(zhuǎn)數(shù)組（它對(duì)應(yīng)的原數(shù)組是有序的），求給定元素在旋轉(zhuǎn)數(shù)組內(nèi)的下標(biāo)（不存在的返回-1）。
例如
有序數(shù)組為{0,1,2,4,5,6,7},它的一個(gè)旋轉(zhuǎn)數(shù)組為{4,5,6,7,0,1,2}.
元素6在旋轉(zhuǎn)數(shù)組內(nèi)，返回2
元素3不在旋轉(zhuǎn)數(shù)組內(nèi)，返回-1
分析托福答案
遍歷一遍，可以輕松搞定，時(shí)間復(fù)雜度為O（n），因?yàn)槭怯行驍?shù)組旋轉(zhuǎn)得到，這樣做肯定不是最優(yōu)解。有序，本能反映用二分查找，舉個(gè)例子看看特點(diǎn)
可以看出中間位置兩段起碼有一個(gè)是有序的（不是左邊，就是右邊），那么就可以在有序的范圍內(nèi)使用二分查找；如果不再有序范圍內(nèi)，就到另一半去找。
參考代碼
復(fù)制代碼
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;
}
復(fù)制代碼
擴(kuò)展
上邊的有求是沒(méi)有重復(fù)的元素，現(xiàn)在稍微擴(kuò)展下，可以有重復(fù)的元素，其他的要求不變。
思路雅思答案
大致思路與原來(lái)相同，這是需要比較A[beg] 與 A[mid]的關(guān)系
A[beg] < A[mid] ----左邊有序
A[beg] > A[mid] ----右邊有序
A[beg] = A[mid] ----++beg
復(fù)制代碼
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;
}