经典算法面试题之：有序旋转数组搜索

我们都知道，搜索一个给定的有序数组时，最快的方法是二分查找。但是如果这个有序数组沿某个方向进行了一定的旋转，比如1，2，3，4，5变成了3，4，5，1，2，如何还能在O(log n)的时间内搜索到某个给定的值呢？

输入输出举例：

这里假设数组中的元素都是唯一的。

一种解法是先找到数组的旋转点，也就是数组中唯一一个比它的下一个元素大的点。

旋转点可以将数组分成左右两个子数组，然后就可以在其中一个子数组中进行二分查找了。

算法过程如下：

1. 将输入数组分成两个连续子数组

2. 用二分查找在其中一个子数组中进行搜索

a )如果被查找值大于数组第一个元素，则在左子数组中搜索

b) 否则在右子数组中搜索

3. 如果找到了，返回索引值，否则返回-1

上述解法可以做进一步的优化，使其在一次二分查找中完成搜索。具体流程为：

1. 找到中点位置mid = (l + h)/2

2. 如果中点值为要找的值，则返回mid

3. 如果arr[l…mid]是有序的

a) 如果被搜索值在arr[l]和arr[mid]之间，则对arr[l…mid]进行递归调用

b) 否则，对arr[mid+1…r]进行递归调用

4. 如果条件3为False，则arr[mid+1…r]必为有序的

a) 如果被搜索值在arr[mid+1]和arr[r]之间，则对arr[mid+1…r]进行递归调用

b) 否则，对arr[l…mid]进行递归调用

代码如下：

小伙伴们，这个算法大家是否已经掌握了呢？

更多精彩内容，请关注CodeTalk