Оптимальность бинарного поиска

Question

Это может быть глупым вопросом, но кто -нибудь знает о доказательстве того, что бинарный поиск является асимптотически оптимальным? То есть, если нам предоставил отсортированный список элементов, в которых единственная разрешенная операция на этих объектах является сравнением, как вы докажите, что поиск не может быть выполнен в O (LG N)? (Кстати, это немного LG N.) Обратите внимание, что я ограничиваю это элементами, где единственная разрешенная операция-это сравнение, поскольку существуют хорошо известные алгоритмы, которые могут победить O (LG N) Если вам разрешено выполнять более сложные операции по данным (см., Например, поиск интерполяции).

Answer 1

Из здесь:

• Количество возможных результатов должно быть как минимум O (n).
• Вы можете представлять решения, принятые алгоритмом узлами «дерева решений»: если элементы сравниваются больше, то это идет дальше, если не идет в другую сторону. Узлы дерева являются состояниями алгоритма, а листья являются результатами. Таким образом, в дереве должен быть как минимум O (n) узлы.
• Каждое дерево на o (n) узлах имеет по крайней мере O (log n) уровни.

Answer 2

Логика проста. Давайте предположим n разные сортированные элементы.

1. 2 возможные результаты 1 сравнения (первый элемент меньше или больше). Таким образом, если одного сравнения достаточно, n <= 2. Анкет В противном случае, если у нас есть 3 элемента (a, b, c) и наш алгоритм имеет 2 возможных результата, один из 3 элементов никогда не будет выбран.
2. 4 возможных результатов из 2 сравнений. Таким образом, если 2 сравнения достаточно, n <= 4.
3. Точно так же, для k сравнения, чтобы быть достаточно n должно быть n <= 2^k.

Отмените последнее неравенство, и у вас будет логарифм: k >= log(2, n).

Answer 3

Как описала Никита, невозможно что -то иметь всегда лучше, чем O (log n).

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

Мы можем сказать, что поиск интерполяции лучше только потому, что:

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

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