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

Question

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

Answer 1

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

[         |         |    .    |         ]
          v1        v2        v3

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

if(cond)
Go Left
else
Go Right

В сравнении с оператором switch.

Answer 9

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

Jacob

Answer 10

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

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

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

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

поднимая оба до степени 3, 3 ^ log2 n против n ^ 2

=> 3 ^ (log2 3. Log3 n) против n ^ 2

=> n ^ (log2 3) против n ^ 2

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

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