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

Question

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

Answer 1

С здесь :

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

Answer 2

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

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

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

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

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

Answer 3

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

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

Поменяйте местами последнее неравенство, и вы получите логарифм: k >= log(2, n).