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

Ответ 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++ реализация

Ответ 2

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

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

-

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

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

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

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

Ответ 3

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

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

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

если X [i] я затем перейдите к середине оставшегося правого

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

Ответ 4

Не нужно думать в терминах любого массива Y, как предложено в answer, с помощью @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
}

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

Ответ 5

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

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

Ответ 6

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

EDIT: Хорошо, я ошибаюсь. Извиняюсь!

Ответ 7

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

//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).

Ответ 8

Да, я считаю, что ты прав. Логарифмический поиск невозможен, так как нет никакого способа уменьшить число данных, которые у нас есть. Нам нужно будет посмотреть на весь индекс в массиве.

@Kos, я не вижу, как сортировка массива будет иметь какое-то значение?

Ответ 9

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

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

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

Ответ 10

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

Пример:

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

Ответ 11

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

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

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]... псевдокод будет выглядеть примерно так.

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)

Ответ 12

Java:

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

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

С++:

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

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