Поиск в отсортированном и повернутом массиве

Question

При подготовке к техническому интервью я наткнулся на этот интересный вопрос:

Вам дан массив, который отсортирован и затем повернут.

пример

Позвольте arr = [1,2,3,4,5], который отсортирован, а затем повернут, скажем дважды вправо, чтобы дать

[4,5,1,2,3]

Теперь, как лучше всего искать в этом отсортированном + повернутом массиве?можно развернуть массив и затем выполнить бинарный поиск.Но это не лучше, чем выполнять линейный поиск во входном массиве, так как оба являются наихудшим случаем O (N).

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

Я понимаю c и c ++

Answer 1

Это можно сделать в O(logN) с помощью слегка измененного двоичного поиска.

Интересное свойство отсортированного + повернутого массива состоит в том, что при его делении на две половины, по крайней мере, одна из двух половин будетвсегда сортировать.

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

, как кажется, правый подмассив не сортируется, а левый подмассив сортируется.

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

[6,7,8,9,1,2,3,4,5]
         ^

Но в в любом случае одна половина (подмассив) должна быть отсортирована .

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

Как только мы находим, какая половина отсортирована, мы можем видеть, присутствует ли ключ в этой половине - простое сравнение с крайностями.

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

Мы отбрасываем одну половину массива в каждом вызове, что делает этот алгоритм O(logN).

Псевдокод:

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid])

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

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

Answer 2

Вы можете выполнить 2 бинарных поиска: сначала найти индекс i такой, что arr[i] > arr[i+1].

Очевидно, (arr\[1], arr[2], ..., arr[i]) и (arr[i+1], arr[i+2], ..., arr[n]) - это отсортированные массивы.

Тогда, если arr[1] <= x <= arr[i], вы выполняете бинарный поиск в первом массиве, а во втором.

Сложность O(logN)

EDIT: код .

Answer 3

В принятом ответе есть ошибка, когда в массиве есть повторяющиеся элементы. Например, arr = {2,3,2,2,2} и 3 - это то, что мы ищем. Тогда программа в принятом ответе вернет -1 вместо 1.

Этот вопрос интервью подробно обсуждается в книге «Взлом интервью». Состояние дублированных элементов специально обсуждается в этой книге. Поскольку в комментарии говорится, что элементами массива могут быть все что угодно, я предлагаю решение в виде псевдокода ниже:

function search( arr[], key, low, high)

    if(low > high)
        return -1

    mid = (low + high) / 2

    if(arr[mid] == key)
        return mid

    // if the left half is sorted.
    if(arr[low] < arr[mid]) {

        // if key is in the left half
        if (arr[low] <= key && key <= arr[mid]) 
            // search the left half
            return search(arr,key,low,mid-1)
        else
            // search the right half                 
            return search(arr,key,mid+1,high)
        end-if

    // if the right half is sorted. 
    else if(arr[mid] < arr[low])    
        // if the key is in the right half.
        if(arr[mid] <= key && arr[high] >= key) 
            return search(arr,key,mid+1,high)
        else
            return search(arr,key,low,mid-1)
        end-if

    else if(arr[mid] == arr[low])

        if(arr[mid] != arr[high])
            // Then elements in left half must be identical. 
            // Because if not, then it's impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high]
            // Then we only need to search the right half.
            return search(arr, mid+1, high, key)
        else 
            // arr[low] = arr[mid] = arr[high], we have to search both halves.
            result = search(arr, low, mid-1, key)
            if(result == -1)
                return search(arr, mid+1, high, key)
            else
                return result
   end-if
end-function

Answer 4

Моей первой попыткой было бы найти с помощью бинарного поиска число примененных вращений - это можно сделать, найдя индекс n, где a [n]> a [n + 1], используя обычный механизм двоичного поиска.Затем выполните обычный двоичный поиск, поворачивая все найденные индексы за смену.

Answer 5

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) / 2);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}

Answer 6

Если вы знаете, что массив повернут на s вправо, вы можете просто выполнить двоичный поиск со сдвигом s вправо.Это O (lg N)

Под этим я подразумеваю инициализацию левого предела для s и права для (s-1) mod N, и выполняю двоичный поиск между ними, немного позаботившисьработать в правильной области.

Если вы не знаете, на сколько массив был повернут, вы можете определить, насколько велик поворот, используя двоичный поиск, который равен O (lg N), затемвыполните сдвинутый двоичный поиск, O (LG N), итоговый итог O (LG N) до сих пор.

Answer 7

вам не нужно сначала вращать массив, вы можете использовать двоичный поиск по повернутому массиву (с некоторыми изменениями)

предположим, что N - это число, которое вы ищете:

readпервое число (arr [start]) и число в середине массива (arr [end]):

• if arr [start]> arr [end] ->первая половина не отсортирована, но вторая половина отсортирована:

  • если arr [конец]> N -> число находится в индексе: (средний + N - arr [конец])

  • если N повторить поиск в первой части массива (см. Конец в середине первой половины массива и т. Д.)

(то же самое, если первая часть отсортирована, а вторая нет)

Answer 8

Если вы знаете, как (далеко) он был повернут, вы все равно можете выполнить бинарный поиск.

Хитрость в том, что вы получаете два уровня индексов: вы делаете б.с. в виртуальном диапазоне 0..n-1, а затем отмените их вращение при поиске значения.

Answer 9

Ответ на вышеупомянутый пост. «Этот вопрос интервью подробно обсуждается в книге« Взлом интервью ». Условие дубликатов элементов специально обсуждается в этой книге. Поскольку в комментарии говорится, что элементы массива могут бытьчто-нибудь, я даю свое решение в виде псевдокода ниже: "

Ваше решение O (n) !!(Последнее условие if, когда вы проверяете обе половины массива на наличие единственного условия, делает его солью линейной сложности по времени)

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

Я не думаю, что есть лучшее решение, чем O (n), для поиска в повернутом отсортированном массиве (с дубликатами)

Answer 10

public class PivotedArray {

//56784321 first increasing than decreasing
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [] data ={5,6,7,8,4,3,2,1,0,-1,-2};

    System.out.println(findNumber(data, 0, data.length-1,-2));

}

static int findNumber(int data[], int start, int end,int numberToFind){

    if(data[start] == numberToFind){
        return start;
    }

    if(data[end] == numberToFind){
        return end;
    }
    int mid = (start+end)/2;
    if(data[mid] == numberToFind){
        return mid;
    }
    int idx = -1;
    int midData = data[mid];
    if(numberToFind < midData){
        if(midData > data[mid+1]){
            idx=findNumber(data, mid+1, end, numberToFind);
        }else{
            idx =  findNumber(data, start, mid-1, numberToFind);
        }
    }

    if(numberToFind > midData){
        if(midData > data[mid+1]){
            idx =  findNumber(data, start, mid-1, numberToFind);

        }else{
            idx=findNumber(data, mid+1, end, numberToFind);
        }
    }
    return idx;
}

}