Один вопрос о бинарном поиске

Ответ 1

Это потому, что 1 сравнение за уровень (как в бинарном поиске) имеет наименьшее количество сравнений в худшем случае любого n-арного поиска. Это связано с тем, что количество сравнений на один уровень увеличивается линейно, когда глубина дерева уменьшается логарифмически. Для n-го поиска поиск наихудшего числа сравнений ((n-1)/log (n)) * log (m), где m - количество элементов в дереве, которое минимизируется при n = 2.

Ответ 2

Поскольку бинарный поиск приводит к минимальному количеству сравнений и поисков. Для простой интуиции нужно разделить на 4 части каждый раз.

[         |         |    .    |         ]
          v1        v2        v3

Теперь вы выполнили 3 поиска и должны сравнить значение, которое вы ищете в худшем, от всех трех значений. Сравните это с двумя итерациями бинарного поиска:

[                   |    .              ]
                    v1
[                   |    .    |         ]
                    v1        v2

Теперь вы сузили диапазон поиска на ту же сумму, но выполнили только 2 поиска и 2 сравнения.

Ответ 3

Разделение массива пополам требует только ОДНОГО оператора сравнения.

Разделение его на три потребует более одного (иногда одного, иногда двух) сравнения.

Wikipedia должно дать вам немного больше объяснений, включая математику за ней

Ответ 4

Binary позволяет легко сравнивать <= или >= или < или > (не помню, что обычно используется). Он чисто разделяет набор, и легко подойти к разделам. Для произвольных наборов данных, как бы вы разделились на разные части? Как бы вы определили, в какую часть вставить что-то? Двоичный поиск принимает поиск O (log n) для поиска. Добавление большего количества компонентов изменило бы это на что-то ближе к O (m * log n), где m - количество разделяемых частей.

Jacob

Ответ 5

Это значительно упрощает логику:

if(cond)
Go Left
else
Go Right

В отличие от оператора switch.

Ответ 6

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

Ответ 7

В первую очередь потому, что трудно решить, как уменьшить диапазон - как интерполировать. Функция сравнения дает трехсторонний ответ - меньше, чем, больше, больше. Но, как правило, сравнение не дает "намного больше" или "намного меньше" в качестве ответа. Действительно, компаратору приходилось бы смотреть на три значения - текущую контрольную точку, искомое значение и либо "верхний конец диапазона", либо "нижний конец диапазона" для оценки пропорционального расстояния.

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

Ответ 8

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

Как показано, для сравнения трех значений требуется (по крайней мере) две операции.

Ответ 9

Собственно, деревья поиска N-way, а не бинарные деревья обычно используются в системах баз данных. Хотя количество сравнений может быть больше O (log2 n), количество операций чтения существенно меньше. Проверьте B-деревья и их варианты.

Ответ 10

Причина состоит в том, что вы на самом деле ничего не получаете от этого: поиск по-прежнему O(log n), только с другой базой.

Ответ 11

Двоичный поиск использует 1 сравнение для сокращения n до n/2. тройной поиск использует 2 сравнения, чтобы сократить n до n/3.

Таким образом, сложность первого равна 1. log2 n, а вторая - log3 n или log3 n ^ 2

log2 n всегда лучше, чем log3 n ^ 2.

Чтобы увидеть это,

повышение как до 3, 3 ^ log2 n vs n ^ 2

= > 3 ^ (log2 3. log3 n) vs n ^ 2

= > n ^ (log2 3) vs n ^ 2

поэтому бинарный поиск выполняется быстрее любого любого поиска. вы сравниваете log2 m vs (m-1).

В качестве альтернативы интерполяционный поиск асимптотически быстрее, чем двоичный поиск с loglogN. Но это не стоит беспокоиться, если ваши данные не огромны. [так что комментарий выше о наилучшем возможном поиске теоретически неверен!]