Хотелось бы написать про хак, который может помочь ускорить двоичный поиск на очень больших массивах.

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

Как с этим бороться? Очень просто. Пусть n -- размер массива. Разобьем массив на блоков длины . Образуем массив B из первых элементов блоков. Теперь, чтобы сделать двоичный поиск в исходном массиве, достаточно сначала поискать элемент в B, а потом в соответствующем отрезке длины в исходном массиве. Таким образом, количество промахов существенно уменьшится.

Абсолютно аналогичная конструкция возможна для любого числа уровней.

Для эксперимента я сравнил std::lower_bound и оптимизированную версию двоичного поиска (трехуровневую) на случайном массиве 32-битных целых чисел размера 2²⁷. Количество запросов равно 10⁷. Машинка: Intel(R) Core(TM) i5 CPU M 430 @ 2.27GHz, 32k/256k/4m cache, 1066 MHz RAM. Система: GNU/Linux 2.6.35, g++ 4.4.5.

Результат:

• std::lower_bound -- 16.6 секунд
• оптимизированный поиск -- 6.6 секунд