Зачем использовать бинарный поиск, если есть троичный поиск?

Question

Я недавно слышал о троичном поиске, в котором мы делим массив на 3 части и сравниваем. Здесь будет два сравнения, но это уменьшит массив до n / 3. Почему люди не используют это так много?

Answer 1

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

Answer 2

Хотя вы получаете одинаковую сложность big-O (ln n) в обоих деревьях поиска, разница в константах.Вы должны сделать больше сравнений для троичного дерева поиска на каждом уровне.Таким образом, разница сводится к k / ln (k) для k-арного дерева поиска.Это имеет минимальное значение при e = 2,7, а k = 2 обеспечивает оптимальный результат.

Answer 3

Я только что опубликовал блог о троичном поиске, и я показал некоторые результаты.Я также предоставил некоторые реализации начального уровня для моего git repo . Я полностью согласен с каждым по поводу теоретической части троичного поиска, но почему бы не попробовать?В соответствии с реализацией эта часть достаточно проста, если у вас есть три года опыта программирования.Я обнаружил, что если у вас есть огромный набор данных, и вам нужно много раз искать его, у троичного поиска есть преимущество.Если вы думаете, что можете добиться большего успеха с троичным поиском, сделайте это.

Answer 4

Теоретически минимум k/ln(k) достигается при e , и, поскольку 3 ближе к e , чем 2, требуется меньше сравнений.Вы можете проверить, что 3/ln(3) = 2.73.. и 2/ln(2) = 2.88.. Причина, по которой двоичный поиск может быть быстрее, состоит в том, что код для него будет иметь меньше ветвей и будет работать быстрее на современных процессорах.

Answer 5

Возможно, вы слышали, что троичные поиски используются в тех загадках, которые включают взвешивание вещей на весах. Эти шкалы могут возвращать 3 ответа: левый светлее, оба одинаковы или левый тяжелее. Таким образом, в троичном поиске требуется только 1 сравнение. Тем не менее, компьютеры используют логическую логику, которая имеет только 2 ответа. Чтобы выполнить троичный поиск, вам нужно сделать 2 сравнения вместо 1. Я предполагаю, что в некоторых случаях это все еще быстрее, как упоминалось в предыдущих постерах, но вы можете видеть, что троичный поиск не всегда лучше, и его более запутанно и менее естественно реализовать на компьютере.