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

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

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

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

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

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

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

[Обновить]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но в целом бинарный поиск — беспроигрышный вариант.

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

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

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