Является ли бинарный поиск оптимальным в худшем случае?

Question

Является ли бинарный поиск оптимальным в худшем случае? Мой инструктор так сказал, но я не смог найти книгу, которая бы подтверждала это. Мы начинаем с упорядоченного массива, и в худшем случае (наихудший случай для этого алгоритма) любой алгоритм всегда потребует больше парных сравнений , чем бинарный поиск.

Многие говорили, что вопрос неясен. Сожалею! Таким образом, ввод - это любой общий отсортированный массив. Я ищу доказательство, которое говорит, что любой алгоритм поиска будет принимать по крайней мере log2 (N) сравнений в худшем случае (наихудший случай для рассматриваемого алгоритма).

Answer 1

Да, бинарный поиск оптимален.

Это легко увидеть, обратившись к теории информации.Требуется log N бит только для идентификации уникального элемента из N элементов.Но каждое сравнение дает только один бит информации.Следовательно, вы должны выполнить log N сравнений, чтобы идентифицировать уникальный элемент.

Более подробно ... Рассмотрим гипотетический алгоритм X, который превосходит бинарный поиск в худшем случае.Для конкретного элемента массива запустите алгоритм и record задаваемые вопросы;последовательность сравнений, которую он выполняет.Или, скорее, запишите ответы на эти вопросы (например, «true, false, false, true»).

Преобразуйте эту последовательность в двоичную строку (1,0,0,1),Назовите эту двоичную строку «сигнатурой элемента относительно алгоритма X».Сделайте это для каждого элемента массива, назначив «подпись» каждому элементу.

Теперь вот ключ.Если два элемента имеют одинаковую сигнатуру, то алгоритм X не может отличить их друг от друга!Все, что алгоритм знает о массиве, - это ответы, которые он получает от вопросов, которые он задает;то есть сравнения, которые он выполняет.И если алгоритм не может различить два элемента, то он не может быть правильным.(Другими словами, если два элемента имеют одинаковую сигнатуру, то есть они приводят к одной и той же последовательности сравнений алгоритмом, какой из них возвращает алгоритм? Противоречие.)

Наконец, докажите, что если каждая сигнатура имеетменьше чем log N битов, то должно существовать два элемента с одинаковой сигнатурой (принцип голубиных отверстий).Готово.

[обновление]

Один быстрый дополнительный комментарий.Выше предполагается, что алгоритм ничего не знает о массиве, кроме того, что он узнает из сравнения.Конечно, в реальной жизни иногда вы что-то знаете о массиве a priori .Например, если я знаю, что массив содержит (скажем) 10 элементов от 1 до 100, и что они различны, а числа от 92 до 100 присутствуют в массиве ...нужно выполнить четыре сравнения даже в худшем случае.

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

Но в общем случае бинарный поиск все еще оптимален.

Answer 2

Наихудший случай для какого алгоритма?Там нет ни одного универсального "худшего случая".Если ваш вопрос ...

«Есть ли случай, когда бинарный поиск требует больше сравнений, чем другой алгоритм?»

Тогда, да, конечно.Простой линейный поиск занимает меньше времени, если элемент оказывается первым в списке.

«Существует ли даже алгоритм с лучшим временем выполнения в худшем случае, чем двоичный поиск?»

Да, в тех случаях, когда вы знаете больше о данных.Например, основополагающее дерево или trie находятся в худшем постоянном времени относительно количества записей (но линейно по длине ключа).

"Существует ли общий алгоритм поиска с лучшимвремя выполнения в худшем случае, чем при бинарном поиске? "

Если вы можете только предполагать, что у вас есть функция сравнения по ключам, нет, лучшим худшим случаем является O (log n).Но есть алгоритмы, которые работают быстрее, но не в широком смысле.

... поэтому я полагаю, что вам действительно придется сначала задать вопрос!

Answer 3

Двоичный поиск имеет наихудшую сложность сравнения O(log(N)) - что является оптимальным для поиска отсортированного массива на основе сравнения.

В некоторых случаях может иметь смысл сделать что-то, кроме поиска, основанного исключительно на сравнении - в этом случае вы можете преодолеть барьер O(log(N)) - то есть проверить интерполяцию поиск.

Answer 4

Я думаю, что вопрос немного неясен, но все же вот мои мысли.

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

Например: массив A = 1, 2, 3, 4, 5, 6 и двоичный поиск по A для 1 будет наихудшим случаем. Принимая во внимание, что для того же массива линейный поиск для 6 будет наихудшим, а не для поиска 1.

Answer 5

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

Но в целом бинарный поиск - безопасная ставка.