Можно ли считать этот алгоритм алгоритмом бинарного поиска?

14

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

Если у меня есть отсортированный массив длины 100, и я вижу, что его начальное поле содержит число 200, а его конечное поле содержит число 400, я, как математик, изучающий человека, мог бы начать поиск вокруг поля 35, если бы я искал число 270, а не поле 50, как в обычном алгоритме двоичного поиска.

Затем, если число в поле 35 массива равно 270, 35 - это индекс, который я искал.

Если это не так, я могу сравнить полученное число (скажем, 280) и повторить операцию, взяв нижнюю часть массива (таким образом, у меня есть 35 полей с начальным полем, содержащим 200, и конечным полем, содержащим 280), если число, которое я нашел, больше, чем то, что я ищу, или верхней части массива (скажем, я получил 260: теперь у меня есть 65 индексов, первый из которых содержит 260, а последний - 400. Ориентировочно, я бы направился к вершине индекс 4 этого подмассива, который является индексом 39 всего массива), если число, которое я получил, меньше числа, которое я ищу.

Вопрос: можно ли считать этот алгоритм алгоритмом двоичного поиска? Если нет, есть ли у него свое имя?

algorithms terminology search-algorithms binary-search user6245072
источник
2
Является ли это бинарным поиском или нет, кажется, просто вопрос мнения. По сути, единственный ответ, который вы можете дать: «Да, он достаточно близок к бинарному поиску, чтобы называть его бинарным поиском» или «Нет, это не так». Аргумент следует.
Дэвид Ричерби

Ответы:

23

Я бы не назвал это бинарным поиском.

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

Я предпочитаю говорить «Время выполнения двоичного поиска в худшем случае - O (log (n))», а не «В зависимости от выбора ограничивающих элементов время выполнения двоичного поиска в худшем случае - O (log (n))». Это означает, что я не могу классифицировать интерполяционный поиск как алгоритм двоичного поиска.

Taemyr
источник
Предположительно, если вы прервете интерполяционный поиск, когда он идет плохо, вы можете сохранить O (log n) в худшем случае и O (log log n) на достаточно линейных данных. Я предполагаю, что что-то вроде «если я не нашел цель после попытки входа n, а затем переключиться на бинарный поиск» будет работать, но мне лень это доказывать. Конечно, будет класс вводных данных, для которого это в два раза дольше, чем для бинарного поиска.
Стив Джессоп
Эта вводная идея интересна. Что, если вместо того, чтобы вводы-убийцы отрицательно влияли на поиск (т. Е. Путем разбиения в конце массива), мы ограничиваем / обрезаем «разделяемый диапазон» до 2-й трети массива или аналогичного. Это будет иметь худший случай log3 (n), но все равно будет пользоваться лучшим журналом (log).
Эндрю Галлаш
1
@ SteveJessop Помните, что асимтотическая сложность не полная картина. O (log n) очень быстро. Кроме того, бинарный поиск делает очень мало работы в каждом цикле. Таким образом, проблема интерполяционного поиска уже заключается в том, что вам нужен очень длинный ввод, чтобы компенсировать тот факт, что вы выполняете больше работы над каждым циклом. Ваше предложение добавляет больше работы к этому. Если я был не в состоянии принять O (n) для данных, которые не были единообразными, я подозреваю, что лучшее решение - пойти на чистый двоичный поиск, а не какой-нибудь гибридный подход.
Taemyr
@SteveJessop: нет необходимости переключать алгоритмы; это можно сделать параллельно. Учитывая диапазон R, вы можете определить точку P1 как обычную среднюю точку для двоичного поиска, а P2 - с помощью интерполяции. Теперь у вас есть три поддиапазона, ни один из которых не может быть больше половины исходного диапазона. Сравните целевое значение как с P1, так и с P2, и вы знаете, в какой из трех поддиапазонов следует переходить.
MSalters
17

Да, это называется интерполяционным поиском . С некоторыми оговорками (в зависимости от вашей вычислительной модели и распределения данных) его ожидаемое время выполнения , лучше, чем бинарный поиск.O(log⁡log⁡n)

Том ван дер Занден
источник
Здорово. Теперь вопрос, могу ли я использовать его для кода ката, но это моя проблема, смеется. Я нахожу это более сложным, чем бинарный поиск, хотя почему бы и нет.
user6245072
Я обнаружил это однажды, когда несколько лет назад написал код для индексации файла журнала. Я также обнаружил, что для моих данных чередование шагов между интерполяцией и двоичным срезом было лучше, чем любой другой вариант сам по себе. Я не уверен, есть ли у этого имя, или это известный эффект.
Нил Слэйтер
@NeilSlater хеджированный поиск интерполяции возможно?
Стив Кокс
@SteveCox: я просто искал этот термин и ничего не нашел. Решил задать это как новый вопрос: cs.stackexchange.com/questions/59750/…
Нил Слейтер
-1

Я думаю, что правильной терминологией будет поиск в дихотомии.

Вы ищете в плоском массиве с последующим обдуманным поиском на основе предполагаемого плоского распределения чисел в нем.

Это соответствует тому, как человек будет искать слово в словаре. Но это может быть очень неэффективно, если распределение данных нерегулярно.

Людовик Зенохате Лагуардетт
источник