Вопрос интервью - Поиск в отсортированном массиве X для индекса i, такого что X [i] = i

Question

Вчера во время интервью мне задали следующий вопрос:

Рассмотрим массив Java или C ++, скажем X, который отсортирован, и в нем нет двух одинаковых элементов. Как лучше всего найти индекс, скажем, i такой, что элемент в этом индексе также равен i. Это X[i] = i.

В качестве пояснения она также привела мне пример:

Array X : -3 -1 0 3 5 7
index   :  0  1 2 3 4 5

Answer is 3 as X[3] = 3.

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

Я просто хотел подтвердить от сообщества, что я прав. Пожалуйста, скажи мне, что я прав:)

Answer 1

Это можно сделать за O(logN) время и O(1) пространство, используя слегка модифицированный двоичный поиск .

Рассмотрим новый массив Y такой, что Y[i] = X[i] - i

Array X : -3 -1   0  3  5  7
index   :  0  1   2  3  4  5
Array Y : -3 -2  -2  0  1  2

Поскольку элементы в X расположены в порядке , элементы в новый массив Y будет в неубывающем порядке. Так что двоичный поиск для 0 в Y даст ответ.

Но создание Y займет O(N) пространства и O(N) времени. Так что вместо создавая новый массив, вы просто изменяете бинарный поиск таким образом, чтобы ссылка на Y[i] заменена на X[i] - i.

Алгоритм:

function (array X) 
       low  = 0
       high = (num of elements in X) - 1

       while(low <= high) 
               mid = (low + high) / 2

               // change X[mid] to X[mid] - mid
               if(X[mid] - mid == 0)
                       return mid

               // change here too
               else if(X[mid] - mid < 0)
                       low = mid + 1;

               else
                       high = mid - 1;
       end while

       return -1 // no such index exists...return an invalid index.

end function

Реализация Java

Реализация C ++

Answer 2

Существуют более быстрые решения, усредняющие O (log n) или в некоторых случаях O (log log n) вместо O (n).Если у вас есть Google для "бинарный поиск" и "интерполяционный поиск" , вы, вероятно, найдете очень хорошие объяснения.

Если массив не отсортирован, тогда даэлемент находится где угодно, и вы не можете попасть в O (n), но это не относится к отсортированным массивам.

-

Некоторые пояснения по запросу интерполяции:

В то время как бинарный поиск касается только сравнения двух элементов в терминах «больше / не больше», при интерполяционном поиске также используются числовые значения .Дело в том, что у вас есть отсортированный диапазон значений от 0 до, скажем, 20000. Вы ищете 300 - бинарный поиск начнется с половины диапазона, с 10000. Интерполяционный поиск предполагает, что 300, вероятно, будет где-то ближе к 0чем 20000, поэтому он сначала проверит элемент 6000 вместо 10000. Затем снова - если он слишком высокий, вернитесь в нижний поддиапазон, а он слишком низкий - в верхний поддиапазон.

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

Обратите внимание, что это то, что человек делает интуитивно, когда ищет что-то всловарь.

Answer 3

Не требуется думать с точки зрения любого массива Y, как это предлагается в answer by @ codaddict.

Используйте бинарный поиск и проверьте средний элемент данного массива, если онниже его индекса, чем нам не нужно проверять любой более низкий индекс, потому что массив отсортирован, и поэтому, если мы переместимся влево, вычтя m индексов и (как минимум) значение m, все последующие элементы также будут слишком маленькими,Например, если arr[5] = 4, то arr[4] <= (4 - 1), arr[3] <= (4 - 2) и так далее.Аналогичная логика может применяться, если средний элемент больше, чем его индекс.

Вот простая реализация Java:

int function(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        while(low <= high) {
            int mid = high - (high - low) / 2;

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

        return -1; // There is no such index
}

Обратите внимание, что приведенное выше решение будет работать, только если все элементы различны.

Answer 4

Я думаю, что это будет быстрее.

Начать с середины списка

Если X [i]> i, то перейти к середине оставшейся левой стороны

если X [i] Продолжайте делать это, и это уменьшит количество возможных элементов вдвое для каждого цикла

Answer 5

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

Затем вы ищите верхнюю половину и продолжаете, пока не найдете элемент или не достигните одного элемента.

Answer 6

Это решение, которое я придумал, и оно работает, если есть дубликаты (я ошибочно упустил из виду, что дубликатов нет).

//invariant: startIndex <= i <= endIndex

int modifiedBsearch(int startIndex, int endIndex)
{
   int sameValueIndex = -1;
   int middleIndex = (startIndex + endIndex) /2;
   int middleValue = array[middleIndex];
   int endValue = array[endIndex];
   int startValue = array[startIndex];

   if(middleIndex == middleValue)
      return middleValue;
   else {
      if(middleValue <= endIndex)
         sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex)

      if(sameValueIndex == -1 && startValue <= middleIndex)
         sameValueIndex = modifiedBsearch(startIndex, middleIndex -1);
   }

   return sameValueIndex;

}

Полагаю, это займет O (log n) времени, но на первый взгляд это не понятно ???

Если вам не повезло, потребуется время O (n log n) (высота дерева стека будет равна log n, и это будет полное дерево с n узлами на последнем уровне, n / 2 рядом с последним и т. Д.).

Таким образом, в среднем это будет между O (log n) и O (n log n).

Answer 7

Java:

public static boolean check (int [] array, int i)
{
    if (i < 0 || i >= array.length)
        return false;

    return (array[i] == i);
}

C ++:

bool check (int array[], int array_size, int i)
{
    if (i < 0 || i >= array_size)
        return false;

    return (array[i] == i);
}

Answer 8

Модифицированной версии бинарного поиска было бы достаточно, я думаю

Предположим, что последовательность

Array : -1 1 4 5 6
Index :  0 1 2 3 4

Result : 1

или

Array : -2 0 1 2 4 6 10
Index :  0 1 2 3 4 5 6 

Result: 4

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

mid <- (first + last )/2

if a[mid] == mid then
       return mid

else if a[mid] < mid then
        recursive call (a,mid+1,last)

else 
         recursive call (a,first,mid-1)

Answer 9

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

Пример:

int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };

Если моя текущая позиция равна 2, и она имеет значение 4, они не равны, и концептуально значение 4 смещено влево. Я могу использовать значение 4 в качестве моей следующей позиции, потому что если значение 4 вне позиции, то все, что меньше 4, также находится вне позиции.

Пример кода для обсуждения:

void main()
{
    int X[] = { -3, -1, 0, 3, 5, 7};
    int length = sizeof(X)/sizeof(X[0]);

    for (int i = 0; i < length;) {
        if (X[i] > i && X[i] < length)
            i = X[i];                 // Jump forward!
        else if (X[i] == i) {
            printf("found it %i", i);
            break;
        } else
            ++i;
    }
}

Answer 10

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

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

После одного сравнения вы уже разложили свой набор данных пополам