常见算法题系列（四）：在循环有序数组中查找指定元素

问题描述：我们都知道，在一个有序数组中查找指定的元素可以使用二分法。那么对于一个循环有序的数组该怎样进行查找呢？

这里所说的循环有序数组，就是把一个有序数组从某个（未知）位置处截为两段，把前一段放到后一段的后面（数组里的元素还是有序的，只不过最小值不一定是数组的第一个元素，而可能是其中的任何一项，从它开始逐项递增，到数组的最后一个元素时再回到第一个元素）。

显然传统的二分法已经无法直接使用了，但考虑一下，如果已经知道分界点位置，那问题就简单多了，只要先判断一下待查元素是在分界点的左侧还是右侧，然后直接对那一侧的半个数组使用二分查找。

那怎么找分界点呢？它的特点是它左边的元素都比右边的元素大。借鉴二分查找的思想，选取中间的元素，拿它跟两端的元素比一比，分析出分界点是在左半边还是右半边，然后在对那半个数组递归处理。

第一个元素应该是分界点左边最小的一个元素，但又不小于分界点右边的所有元素。那么如果中间元素比它大，分界点只能在中间元素的右边；反之，如果中间元素比它小，分界点就一定在左半边。如果二者相等，就需要比较再拿最后一个元素来比较，如果中间元素比最后一个元素大，分界点在右边；反之，如果中间元素比最后一个元素小，分界点在左边。如果还相等，那麻烦就来了。

考虑下面这张图中的两种情况（A和B），显然，第一次二分处理的时候，这两种情况下，第一个、中间的和最后一个元素都是彼此相等的，但分界点却可能在左边也可能在右边。

可见先找分界点的方法在这种情况下是行不通的。

另外一种方法，是直接使用一种变体的二分法，相当于把找分界点跟搜索指定数值结合起来，也就是每次二分的时候，除了跟中间值做比较外，也要跟两端的数值做比较，以此来确定对哪一半进行分治递归处理。然而这种方法对于上图中的情况依旧是无能为力的。

对于类似于上图中的输入，能否用log n时间找到指定元素呢？我还没想好-_-

我们还是先考虑没有重复值的情况吧，按照第二种想法（变体的二分法）写出算法，时间复杂度是log n：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def CycleBSearch(arr, val): left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) / 2 if val == arr[mid]: return mid # found val   if arr[left] <= arr[mid]: if arr[left] <= val < arr[mid]: right = mid - 1 # val is in left side else: left = mid + 1 # val is in right side else: if arr[left] > val > arr[mid]: left = mid + 1 # val is in right side else: right = mid - 1 # val is in left side return -1 # cannot find val