Хотелось бы написать про хак, который может помочь ускорить двоичный поиск на очень больших массивах.
Дело в том, что обычный двоичный поиск весьма неэффективен с точки зрения кэша: вначале, пока границы поиска далеко друг от друга, запросы к массиву будут далеки друг от друга, что породит много кэш-промахов.
Как с этим бороться? Очень просто. Пусть n -- размер массива. Разобьем массив на блоков длины . Образуем массив B из первых элементов блоков. Теперь, чтобы сделать двоичный поиск в исходном массиве, достаточно сначала поискать элемент в B, а потом в соответствующем отрезке длины в исходном массиве. Таким образом, количество промахов существенно уменьшится.
Абсолютно аналогичная конструкция возможна для любого числа уровней.
Для эксперимента я сравнил std::lower_bound и оптимизированную версию двоичного поиска (трехуровневую) на случайном массиве 32-битных целых чисел размера 227. Количество запросов равно 107. Машинка: 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 секунд