Если вы хотите использовать упорядоченную структуру данных, бинарный поиск является оптимальным в асимптотическом смысле.Однако, если вы используете вспомогательное дерево, вы можете получить большой постоянный коэффициент производительности по времени, если вы обратите внимание на локальность.
В частности, если вы обращаетесь к своим данным с диска, то время доступа к диску будет доминировать во всемостальное.В этом случае вы хотите уменьшить количество отдельных блоков данных, к которым необходимо получить произвольный доступ с диска.Это то, что делают B-деревья, B +-деревья и тому подобное: они хранят данные в форме дерева и обеспечивают большую разветвленность узлов, поэтому они могут ограничивать глубину и, следовательно, не требуютмного случайных поисков.
При доступе к данным в оперативной памяти вы можете сделать нечто подобное, обращая внимание на строки кэша; Деревья Джуди являются одним из примеров этого.
Если вы делаете точное совпадение, вы можете выполнять хеширование в постоянное время - независимо от того, упорядочены ваши числа или нет.Однако хеширование может привести к значительным накладным расходам во времени и пространстве, и упорядоченные методы часто являются конкурентоспособными, поэтому вы действительно хотите принимать решения в каждом конкретном случае.