Есть ли название для этого типа бинарного поиска?

Question

При написании некоторого кода сегодня я столкнулся с обстоятельством, которое заставило меня написать бинарный поиск, которого я никогда раньше не видел. Есть ли у этого бинарного поиска имя, и действительно ли это «бинарный» поиск?

Мотивация

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

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

int findIndexClosestTo(int x);

Звонки на findIndexClosestTo() всегда следуют этому правилу:

Если последний результат findIndexClosestTo() был i, то индексы ближе к i имеют большую вероятность быть результатом текущего вызова на findIndexClosestTo().

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

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

Алгоритм

Учитывая приведенный выше случай, мы знаем, что последний результат findIndexClosestTo() был i (если это фактически первый раз, когда вызывается функция, i по умолчанию равен среднему индексу списка, для простоты, хотя отдельный двоичный поиск для поиска результата первого вызова на самом деле был бы быстрее), и функция была вызвана снова. Учитывая новое число x, мы следуем этому алгоритму, чтобы найти его индекс:

1. interval = 1;
2. Номер, который мы ищем, x, расположен на i? Если это так, верните i;
3. Если нет, определите, находится ли x выше или ниже i. (Помните, список отсортирован.)
4. Переместить interval индексов в направлении x.
5. Если мы нашли x в нашем новом местоположении, верните это местоположение.
6. Двойной interval. (т.е. interval *= 2)
7. Если мы прошли x, вернемся interval индексы, установите interval = 1, перейдите к 4.

Учитывая приведенное выше правило вероятности (под заголовком «Мотивация»), мне представляется, что это наиболее эффективный способ найти правильный индекс. Вы знаете более быстрый способ?

Answer 1

В худшем случае ваш алгоритм будет O ((log n) ^ 2).

Предположим, вы начинаете с 0 (с интервалом = 1), а искомое значение фактически находится в местоположении 2 ^n - 1.

Сначала вы проверите 1, 2, 4, 8, ..., 2 ^ (n-1), 2 ^ n.К сожалению, это переходит, поэтому вернитесь к 2 ^ (n-1).

Затем вы проверяете 2 ^ (n-1) +1, 2 ^ (n-1) +2, ...,2 ^ (n-1) + 2 ^ (n-2), 2 ^ (n-1) + 2 ^ (n-1).Этот последний член равен 2 ^ n, так что, к сожалению, снова промахнулся.Вернитесь к 2 ^ (n-1) + 2 ^ (n-2).

И так далее, пока, наконец, не достигнете 2 ^ (n-1) + 2 ^ (n-2) +... + 1 == 2 ^ n - 1.

Первый выброс произошел за n шагов.Следующий предпринял (log n) -1 шаг.Следующее заняло (log n) - 2 шага.И так далее.

Итак, в худшем случае вы сделали 1 + 2 + 3 + ... + log n == O ((log n) ^ 2) шагов.

А лучшеИдея, я думаю, состоит в том, чтобы переключиться на традиционный бинарный поиск, как только вы перезапустите в первый раз.Это сохранит O (log n) производительность алгоритма в наихудшем случае, но будет немного быстрее, когда цель действительно будет рядом.

Я не знаю имени для этого алгоритма, но мне нравитсяЭто.(По странному стечению обстоятельств я мог бы использовать его вчера. Действительно.)

Answer 2

Что вы делаете, это (ИМХО) версия Интерполяционный поиск

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

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

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

1. Начните медленно
   1. Двойной интервал
   2. в случае сбоя пакета перезапустите его с последнего успешного пакета. / Перезапустите от размера пакета по умолчанию .. 3.

Answer 3

Ваша процедура типична для процедур интерполяции. Вы не теряете много, если вы называете его случайными числами (~ стандартный двоичный поиск), но если вы называете его с медленно растущими числами, поиск правильного индекса не займет много времени.

Таким образом, это разумное поведение по умолчанию для поиска упорядоченной таблицы для целей интерполяции.

Этот метод подробно обсуждается в 3-й редакции «Числовых рецептов», раздел 3.1.

Answer 4

Это говорит с макушки головы, так что мне нечего подкрепить, кроме чувства кишки!

На шаге 7, если мы прошли x, может быть быстрее сократить вдвое interval и вернуться к x - эффективно, interval = -(interval / 2), а не сбрасывать interval в 1.

Мне придется набросать несколько цифр на бумаге, хотя ...

Редактировать: Извинения - я говорю глупости выше: игнорировать меня! (И я уйду, и у меня будет правильный подумать об этом на этот раз ...)