我们要在圆形排序数组中搜索给定元素，其复杂度不大于O(log n)。
示例：搜索13在{5,9,13,1,3}。

我的想法是将圆形数组转换为常规排序的数组，然后对结果数组进行二进制搜索，但是我的问题是我提出的算法很愚蠢，它O(n)在最坏的情况下会采用：

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

然后根据以下关系确定第ith个元素的相应索引：

(i + minInex - 1) % a.length

很明显，我的算法（从循环到常规）的转换可能需要O（n），因此我们需要一个更好的算法。

根据ire_and_curses的想法，这是Java中的解决方案：

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1;
    if(a[mid] == x){
        return mid;
    }
    //a variable to indicate which half is sorted
    //1 for left, 2 for right
    int sortedHalf = 0;
    if(a[low] <= a[mid]){
        //the left half is sorted
        sortedHalf = 1;
        if(x <= a[mid] && x >= a[low]){
            //the element is in this half
            return binarySearch(a, low, mid, x);
        }
    }
    if(a[mid] <= a[high]){
        //the right half is sorted
        sortedHalf = 2;
        if(x >= a[mid] && x<= a[high] ){
            return binarySearch(a, mid, high, x);
        }
    }
    // repeat the process on the unsorted half
    if(sortedHalf == 1){
        //left is sorted, repeat the process on the right one
        return circularArraySearch(a, mid, high, x);
    }else{
        //right is sorted, repeat the process on the left
        return circularArraySearch(a, low, mid, x);
    }
}

希望这会起作用。