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

Мотивация

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

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

int findIndexClosestTo(int x);

Вызовы findIndexClosestTo () always следуют этому правилу:

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

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

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

Алгоритм

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

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

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