要求
给定一没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-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; }
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3687583.html，如需转载请自行联系原作者
