Вопросы Теги

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

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

Надо надеяться, это будет работать.

27
задан Cœur 10 September 2017 в 06:46
поделиться

6 ответов

Не очень элегантно, но безумно - просто используйте двоичный поиск, чтобы найти стержень повернутого массива, а затем снова выполните двоичный поиск, компенсируя смещение стержня. Глупо выполнять два полных поиска, но условие выполняется, поскольку O (log n) + O (log n) == O (log n). Будь простым и глупым (тм)!

9
ответ дан 28 November 2019 в 04:32
поделиться

гирджис: Неуместно публиковать вопросы на собеседовании, думаю, вы не получили работу: - (

Используйте специальную функцию 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 из каждого элемента при доступе к нему и используйте обычное сравнение.

-1
ответ дан 28 November 2019 в 04:32
поделиться

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

(index + start-index) mod array-size

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

0
ответ дан 28 November 2019 в 04:32
поделиться

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

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

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

0
ответ дан 28 November 2019 в 04:32
поделиться

У вас есть три значения: l , m , h для значений нижнего, среднего и высокого индексов вашего поиска. Если бы вы думали, что это так, вы бы продолжили поиск каждой возможности: 

// normal binary search
l < t < m    - search(t,l,m)
m < t < h    - search(t,m,h)

// search over a boundary
l > m, t < m - search(t,l,m)
l > m, t > l - search(t,l,m)
m > h, t > m - search(t,m,h)  
m > h, t < h - search(t,m,h)

Это вопрос рассмотрения того, где может быть целевое значение, и поиска в этой половине пространства. Максимум одна половина пространства будет иметь обертку, и легко определить, находится ли целевое значение в той или другой половине.

Это своего рода мета-вопрос - думаете ли вы о двоичном поиске в терминах того, как он часто представляется - нахождение значения между двумя точками или, в более общем смысле, как повторяющееся разделение абстрактного пространства поиска.

5
ответ дан 28 November 2019 в 04:32
поделиться
Другие вопросы по тегам:

Похожие вопросы: