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

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

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

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

Также обратите внимание, что эта последовательность обобщается на линейный поиск, если мы продолжим

Binary search
Ternary search
...
...
n-ary search ≡ linear search

Таким образом, в n-арном поиске у нас будет «одно только СРАВНЕНИЕ», которое может занять до n фактических сравнения.

Почему вы думаете, что троичный поиск должен быть быстрее?

Среднее число сравнений:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

Наихудшее число сравнений:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Итак, похоже, что троичный поиск хуже.

Единственный способ, которым троичный поиск может быть быстрее, чем двоичный поиск, - это если трехстороннее определение раздела может быть выполнено менее чем примерно в 1,55 раза дороже, чем двухстороннее сравнение. Если элементы хранятся в отсортированном массиве, трехстороннее определение будет в среднем в 1,66 раза дороже, чем двухстороннее определение. Однако, если информация хранится в дереве, стоимость выборки информации высока по сравнению со стоимостью фактического сравнения, а локальность кеша означает, что стоимость случайной выборки пары связанных данных не намного хуже, чем стоимость выборки одного. данные, троичное или n-стороннее дерево могут значительно повысить эффективность.

Для поиска 1 миллиарда (миллиард США - 1 000 000 000) отсортированных элементов потребуется в среднем около 15 сравнений с бинарным поиском и около 9 сравнений с тройным поиском - не очень большое преимущество. И обратите внимание, что каждое «троичное сравнение» может включать 2 фактических сравнения.

Тройной поиск по-прежнему даст вам ту же асимптотическую сложность O (log N) времени поиска и усложнит реализацию.

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

Вау. Ответы, получившие наибольшее количество голосов, по-моему, не дотягивают до этого.

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

B-деревья могут иметь несколько ветвей в каждом узле; B-дерево порядка 3 - это троичная логика. Каждый шаг вниз по дереву будет занимать два сравнения вместо одного, и это, вероятно, приведет к замедлению процессорного времени.

B-деревья, однако, довольно распространены. Если вы предполагаете, что каждый узел дерева будет храниться где-то отдельно на диске, вы будете тратить большую часть времени на чтение с диска... и процессор не будет узким местом, а диск будет. Итак, вы берете B-дерево со 100 000 дочерних элементов на узел, или что там еще едва помещается в один блок памяти. B-деревья с таким коэффициентом ветвления редко будут иметь высоту более трех узлов, и для поиска в огромном, огромном наборе данных вам потребуется всего три чтения с диска - три остановки на узком месте.

Обзор:

• Троичные деревья не поддерживаются аппаратными средствами, поэтому они работают менее быстро.
• B-деревья с порядками намного, намного, намного выше 3 обычно используются для дисковой оптимизации больших наборов данных; как только вы перешагнули через 2, перешагните через 3.

«Тернарный» (тройной?) Поиск более эффективен в лучшем случае, который будет включать поиск первого элемента (или, возможно, последнего, в зависимости от того, какое сравнение вы выполняете первым). Для элементов дальше от конца, который вы проверяете в первую очередь, в то время как два сравнения сужали бы массив каждый раз на 2/3, те же два сравнения с двоичным поиском сужали бы пространство поиска на 3/4.

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