要求
给定一没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-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;
}