Пусть у нас есть множество. Имеем на нем все операции, не зависящие от его размера. Существует ли алгоритм поиска в этом множестве, более быстрый чем Log(2,n)?

Грубо говоря, поиск половинным делением самый быстрый?

Хм.. ну можно к примеру сделать индексацию по значению хеша.
тогда скорость поиска будет вообще константной.
т.е. :
char * a = "abcdefght";
table [HashFunc(a)]=a;
вот и все.
Зы. Некоторые варианты поиска описаны у Юрова. Остальные - у Кнута.

Я бы сказал, что на очень больших выборках выигрывают AVL-деревья. Бинарный поиск очень неплох. Действительно неплох. Но сбалансированное дерево, вероятно, будет лучше. Может и красно-черные использовать стоит...

Асимптотически самый быстрый - интерполяционный поиск O(log(log(n))). Но вот константа... :)
А мне больше всего нравятся trie, btree, patricia.

Хороший результат даст комбинированный поиск. Например, хеширование+бинарный поиск. Т.е. делим всё множество на кластеры хэш-функцией, а внутри кластера ищем при помощи бинарного поиска. Получаем малые затраты на вставку и очень быстрый поиск с известной верхней границей: даже если подведёт хэш-функция, поиск займёт не более чем O(log2(N)).

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