Почему бинарный поиск называется бинарным поиском?

9

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

Обновление 05.19: Меня интересует этот вопрос, потому что один из моих студентов написал в своей диссертации, что название происходит от объяснения ниже (1). До сих пор я думал / слышал, что это происходит из объяснения (2). Я бы чувствовал себя плохо как из-за того, что допустил неправильную вещь в своей диссертации, так и из-за того, что сказал ему убрать это, если это могло бы быть правильно.

(1) Рассмотрим поиск целого числа в интервале . Мы можем найти его с помощью вопросов, задавая в шаге я ^ {е} двоичного разряда числа.[0,2n1]i i t hniith

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

И да, я знаю, что (2) может дать тот же алгоритм, что и (1), но здесь дело не в этом. (2) может также применяться для более общих задач.

domotorp
источник
1
Также обратите внимание, что вопрос требует ссылок. Пожалуйста, не отвечайте, говоря, что это из-за такой-то причины, без указания надежного источника.
Дэвид Ричерби
1
@DavidRicherby, нет, любопытство не является достаточной мотивацией для требования «надежной» ссылки. Любопытство было бы достаточной мотивацией для вопроса «Почему бинарный поиск называется бинарным поиском?», Но это не является достаточной причиной, чтобы требовать ссылки / надежного источника, и это не является достаточной причиной, чтобы сказать «не отвечайте с объяснением; я только хочу надежных источников ". Если ОП встречал несколько противоречивых объяснений, то ОП должен рассказать нам о них в вопросе (обратите внимание, что вопрос Math.SE не привел к противоречивым объяснениям).
DW
3
Я думаю, вам следует начать с объяснения. У нас может быть представление о доверии, которое они должны получить. И это может помочь, если вы дадите свое собственное, предпочтительно точное, определение того, что вы называете бинарным поиском, так что мы можем с уверенностью говорить об одной и той же концепции или альтернативно дать ссылку на такое определение.
Бабу
2
Том 3 Кнута TAoCP, кто-нибудь? Мой в офисе ...
Хендрик Ян
3
Связанный: hsm.stackexchange.com/questions/2200/…
Кайл Джонс

Ответы:

1

Объяснение (2) является хорошим объяснением.

(2) является лучшим объяснением двух, потому что оно в целом применимо ко всем видам бинарного поиска, а не только к одному конкретному случаю. (1) не является необоснованным способом думать об этом - он просто не такой общий или полный, как (2).

Я не думаю, что вам нужно чувствовать, что студент должен исправить это утверждение. Было бы не стыдно, если студент дал объяснение (1) в своей диссертации, поэтому вам не нужно чувствовать себя плохо. Но если вы хотите научить их чему-то, вы можете рассказать им об объяснении (2) и о том, как бинарный поиск является более общим, и почему название «бинарный поиск» также подходит для общего алгоритма. Но это второстепенный вопрос, и я бы не считал его проблематичным или смущающим, если бы они оставили все как есть.

DW
источник
нет ссылок! больше похоже на исторический вопрос :(
vzn
1

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

Более общая концепция поиска «разделяй и властвуй» путем многократного разделения пространства поиска называется дихотомическим поиском (буквально: «который разрезает пополам»). Использование дихотомии может быть рассмотрено в других контекстах, так как у вас есть что разделить. На самом деле это первое выражение, которое я выучил (в старшей школе, я думаю, и это было давно), в том числе в тех случаях, когда вы могли бы назвать его двоичным.

Afaik, «дихотомический» не означает, что две части (почти) равны.

Я не знаю, что двоичный файл зарезервирован для поиска в пространстве размером .2n

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

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

Вы пример (2) неясен. Просто разделение на две части следует назвать дихотомическими. Теперь, когда вы, кажется, выдвинули гипотезу (странно), как сделать 2 равные части, я не уверен.

Но игра в догадки, где люди задают вопросы, на которые да или нет, явно дихотомична.

Мое собственное предположение, без ссылки:

Первоначальное выражение, вероятно, было «дихотомичным», но с популярностью двоичных систем, двоичного компьютера и т. Д. Термин «двоичный» стал более популярным.

Еще один фактор, который мог сыграть важную роль, заключается в том, что бинарный поиск (а также дихотомический) основан на бинарном выборе. Теперь выражение « дихотомический выбор » существует, но используется гораздо реже, чем « бинарный выбор », который встречается в сети примерно в 6 раз чаще.

Так что это могло повлиять на это. Мы должны помнить, что, хотя мы в основном погружены в двоичное число (я имею в виду нас, компьютерный ученый), большинство людей не интересуются двоичными числами и не занимаются ими, но будут легко говорить о двоичном выборе. Это правда, что бинарный поиск - тема для компьютерного ученого, но, если не считать надежной ссылки на обратное, я не поверю, что она напрямую связана с двоичными числами.

Babou
источник
«Согласно Википедии, бинарный поиск касается поиска в массиве отсортированных значений». - Ну, я не так читаю Википедию. Если Википедия говорит, что она должна быть в массиве, чтобы считаться бинарным поиском, то, я думаю, Википедия спорна об этом - но статья в Википедии, похоже, не говорит этого. Далее в статье в Википедии говорится, что бинарный поиск «позволяет осуществлять поиск по аргументу любой монотонной функции для точки, в которой функция достигает произвольного значения», а не для поиска в массиве.
DW
«Более общая концепция« разделяй и властвуй »путем многократного разделения пространства поиска называется дихотомическим поиском» - это не соответствует моему собственному опыту. Я обычно слышу это называется бинарный поиск.
DW
@DW Как я уже говорил, моей памяти не так много, чтобы доверять. Но бинарный поиск, или даже «разделяй и властвуй» - это алгоритмическая терминология, которая пришла к нам с компьютерами. Но я думаю, что не было много компьютеров, когда я впервые услышал о дихотомическом поиске. Тогда хороший печатный справочник был бы намного лучше, чем моя (е) больная память. Что касается википедии, я не прочитал всю статью. По сути, я не думал, что получу окончательный ответ ... и у меня есть некоторые сомнения, что он есть. Идея общая, терминология хорошая, и каждый должен был адаптировать ее к любой проблеме.
Бабу
1

Кнут (V.3 Pg. 82) дает Mauchly в качестве источника для бинарного поиска; он используется для поиска точки вставки во время сортировки, которая затем перетасовывает элементы вперед, чтобы создать вакансию, в процессе, называемом двоичной вставкой.

Так что (2) будет действительным, но я не вижу оригинальной статьи; это скрыто здесь: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

KWillets
источник
1

Я попытался найти ссылку Mauchly, на которую ссылается Кнут, но моя библиотека, похоже, не поместила их копию.

А пока рассмотрим следующие ранние цитаты для «бинарного поиска»:

Я отмечу, как в первой цитате 1958 года используются кавычки вокруг «двоичного», но к третьей цитате в 1960 году упоминается двоичный поиск без дальнейшего описания или объяснения. Намек на «поиск по разделу» предполагает, что объяснение 2) ближе, но требуется дополнительная проверка.

mhum
источник