Поиск элемента в круговом отсортированном массиве

Question

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

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

Answer 1

Вот идея, связанная с бинарным поиском. Просто продолжайте резервное копирование своего индекса для правой границы индекса массива, левая граница индекса сохраняется в размере шага:

step = n
pos = n
while( step > 0 ):
    test_idx = pos - step   #back up your current position
    if arr[test_idx-1] < arr[pos-1]:
        pos = test_idx
    if (pos == 1) break
    step /= 2 #floor integer division
return arr[pos]

Чтобы избежать (pos == 1), мы могли бы вернуться обратно по кругу (перейти к отрицательным числам) и взять (pos-1) mod n.

Answer 2

Отметьте этот коэффициент,

    def findkey():
    key = 3

    A=[10,11,12,13,14,1,2,3]
    l=0
    h=len(A)-1
    while True:
        mid = l + (h-l)/2
        if A[mid] == key:
            return mid
        if A[l] == key:
            return l
        if A[h] == key:
            return h
        if A[l] < A[mid]:
            if key < A[mid] and key > A[l]:
                h = mid - 1
            else:
                l = mid + 1
        elif A[mid] < A[h]:
            if key > A[mid] and key < A[h]:
                l = mid + 1
            else:
                h = mid - 1

if __name__ == '__main__':
    print findkey()

Answer 3

public static int _search(int[] buff, int query){
    int s = 0;
    int e = buff.length;
    int m = 0; 

    while(e-s>1){
        m = (s+e)/2;
        if(buff[offset(m)] == query){
            return offset(m);
        } else if(query < buff[offset(m)]){
            e = m;
        } else{
            s = m;
        }
    }

    if(buff[offset(end)]==query) return end;
    if(buff[offset(start)]==query) return start;
    return -1;
}

public static int offset(int j){
    return (dip+j) % N;
}

Answer 4

guirgis: Хромо задавать вопросы на собеседовании, думаю, вы не получили работу: - (

Используйте специальную функцию cmp, и вам потребуется всего один проход с обычным двоичным поиском. Что-то вроде:

def rotatedcmp(x, y):
  if x and y < a[0]:
    return cmp(x, y)
  elif x and y >= a[0]:
    return cmp(x, y)
  elif x < a[0]:
    return x is greater
  else:
    return y is greater

Если вы можете зависеть от недопустимого значения int, вычтите [0] - MIN_INT из каждого элемента при доступе к нему и используйте регулярное сравнение.

Answer 5

Вы просто используете простой двоичный поиск, как если бы это был обычный отсортированный массив. Единственная хитрость в том, что вам нужно повернуть индексы массива:

(index + start-index) mod array-size

где start-index - это смещение первого элемента в круговом массиве.

Answer 6

Вы можете использовать бинарный поиск, чтобы найти местоположение наименьшего элемента и уменьшить его до O (Log n) .

Вы можете найти местоположение по (это просто набросок алгоритма, он неточный, но вы можете понять из него):
1. я <- 1 <br> 2. j <- n <br> 3. пока я 3.1. k <- (j-i) / 2 <br> 3.2. если arr [k]

После нахождения местоположения наименьшего элемента вы можете рассматривать массив как два отсортированных массива.