Мы хотим найти данный элемент в круговом отсортированном массиве по сложности, не превышающей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;
    }
}

тогда соответствующий индекс i-го элемента будет определяться из следующего соотношения:

(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);
    }
}

Надеюсь, это сработает.