Подтвердить что ты не робот

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете сделать это, воспользовавшись тем, что массив отсортирован, за исключением специального случая значения поворота и одного из его соседей.

  • Найти среднее значение массива a.
  • Если a[0] < a[mid], то все значения в первая половина массива отсортирован.
  • Если a[mid] < a[last], то все значения во второй половине массив отсортированы.
  • Возьмите отсортированный и проверьте, соответствует ли ваша стоимость лежит в нем (по сравнению с максимум idx в этой половине).
  • Если это так, просто двоичный поиск эта половина.
  • Если это не так, должен быть в несортированной половине. принимать что половина и повторить этот процесс, определяя, какая половина этой половины сортируется и т.д.

Ответ 2

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

Ответ 3

У вас есть три значения: 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)

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

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

Ответ 4

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

Метод выглядит следующим образом:

private static int circularBinSearch ( int key, int low, int high )
{
    if (low > high)
    {
        return -1; // not found
    }

    int mid = (low + high) / 2;
    steps++;

    if (A[mid] == key)
    {
        return mid;
    }
    else if (key < A[mid])
    {
        return ((A[low] <= A[mid]) && (A[low] > key)) ?
               circularBinSearch(key, mid + 1, high) :
               circularBinSearch(key, low, mid - 1);
    }
    else // key > A[mid]
    {
        return ((A[mid] <= A[high]) && (key > A[high])) ?
               circularBinSearch(key, low, mid - 1) :
               circularBinSearch(key, mid + 1, high);
    }
}

Теперь, чтобы облегчить любые заботы, вот хороший маленький класс, который проверяет алгоритм:

public class CircularSortedArray
{
    public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 
                                   91, 99, 1, 4, 11, 14, 15, 17, 19};
    static int steps;

    // ---- Private methods ------------------------------------------

    private static int circularBinSearch ( int key, int low, int high )
    {
        ... copy from above ...
    }

    private static void find ( int key )
    {
        steps = 0;
        int index = circularBinSearch(key, 0, A.length-1);
        System.out.printf("key %4d found at index %2d in %d steps\n",
                          key, index, steps);
    }

    // ---- Static main -----------------------------------------------

    public static void main ( String[] args )
    {
        System.out.println("A = " + Arrays.toString(A));
        find(44);   // should not be found
        find(230);
        find(-123);

        for (int key: A)  // should be found at pos 0..18
        {
            find(key);
        }
    }
}

Это даст вам результат:

A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key   44 found at index -1 in 4 steps
key  230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key   23 found at index  0 in 4 steps
key   27 found at index  1 in 3 steps
key   29 found at index  2 in 4 steps
key   31 found at index  3 in 5 steps
key   37 found at index  4 in 2 steps
key   43 found at index  5 in 4 steps
key   49 found at index  6 in 3 steps
key   56 found at index  7 in 4 steps
key   64 found at index  8 in 5 steps
key   78 found at index  9 in 1 steps
key   91 found at index 10 in 4 steps
key   99 found at index 11 in 3 steps
key    1 found at index 12 in 4 steps
key    4 found at index 13 in 5 steps
key   11 found at index 14 in 2 steps
key   14 found at index 15 in 4 steps
key   15 found at index 16 in 3 steps
key   17 found at index 17 in 4 steps
key   19 found at index 18 in 5 steps

Ответ 5

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

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

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

Ответ 6

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

(index + start-index) mod array-size

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

Ответ 7

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

Ответ 8

Проверьте этот коэффициент,

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

Ответ 9

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

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.

Ответ 10

Я думаю, вы можете найти смещение, используя этот код:

public static int findOffset(int [] arr){
        return findOffset(arr,0,arr.length-1);
    }
private static int findOffset(int[] arr, int start, int end) {

    if(arr[start]<arr[end]){
        return -1;
    }
    if(end-start==1){
        return end;
    }
    int mid = start + ((end-start)/2);
    if(arr[mid]<arr[start]){
        return findOffset(arr,start,mid);
    }else return findOffset(arr,mid,end);
}

Ответ 11

Ниже приведена реализация на C, использующая двоичный поиск.

int rotated_sorted_array_search(int arr[], int low, int high, int target)
{
    while(low<=high)
    {
        int mid = (low+high)/2;

        if(target == arr[mid])
            return mid;

        if(arr[low] <= arr[mid])
        {
            if(arr[low]<=target && target < arr[mid])
            {
                high = mid-1;
            }
            else
                low = mid+1;
        }
        else
        {
            if(arr[mid]< target && target <=arr[high])
            {
                low = mid+1;
            }
            else
                high = mid-1;
        }
    }
    return -1;
}

Ответ 12

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

function search(array, query, left, right) {
  if (left > right) {
    return -1;
  }

  var midpoint = Math.floor((left + right) / 2);
  var val = array[midpoint];
  if(val == query) {
    return midpoint;
  }

  // Look in left half if it is sorted and value is in that 
  // range, or if right side is sorted and it isn't in that range.
  if((array[left] < array[midpoint] && query >= array[left] && query <= array[midpoint])
    || (array[midpoint] < array[right] 
        && !(query >= array[midpoint] && query <= array[right]))) {
    return search(array, query, left, midpoint - 1);
  } else {
    return search(array, query, midpoint + 1, right);
  }
}

Ответ 13

Простой двоичный поиск с небольшим изменением.

Индекс вращающейся матрицы = (i + pivot)% size

pivot - индекс я + 1, где a [i] > a [i + 1].

#include <stdio.h>
#define size 5
#define k 3
#define value 13
int binary_search(int l,int h,int arr[]){

int mid=(l+h)/2;

if(arr[(mid+k)%size]==value)
    return (mid+k)%size;

if(arr[(mid+k)%size]<value)
    binary_search(mid+1,h,arr);
else
    binary_search(l,mid,arr);
}

int main() {
    int arr[]={5,9,13,1,3};
    printf("found at: %d\n", binary_search(0,4,arr));
    return 0;
}

Ответ 14

Простой метод в Ruby

def CircularArraySearch(a, x)
  low = 0
  high = (a.size) -1

  while low <= high
    mid = (low+high)/2
    if a[mid] == x
      return mid
    end
    if a[mid] <= a[high]
      if (x > a[mid]) && (x <= a[high])
        low = mid + 1
      elsif high = mid -1
      end
    else
      if (a[low] <= x) && (x < a[mid])
        high = mid -1
      else
        low = mid +1
      end
    end
  end
  return -1
end

a = [12, 14, 18, 2, 3, 6, 8, 9]
x = gets.to_i
p CircularArraySearch(a, x)

Ответ 15

Хотя одобренный ответ является оптимальным, но мы также можем использовать аналогичный и более чистый алгоритм.

  • запустите двоичный поиск, чтобы найти элемент сворачивания (где массив повернут). O(logn)
  • левая половина поворота будет отсортирована в порядке убывания, запустите обратный двоичный поиск здесь для ключа. O(logn)
  • правая половина поворота будет сортироваться в порядке возрастания, запустите прямой двоичный поиск в этой половине для ключа. O(logn)
  • возвращает найденный индекс ключа с шага 2 и 3.

Общая сложность времени: O(logn)

Мысли приветствуются.

Ответ 16

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 underflow, вычитайте [0] - MIN_INT из каждого элемента по мере его доступа и используйте регулярное сравнение.