03.06.2026
Бинарный поиск - это понятно. А как насчет четвертичного поиска?
Даниэль Лемир показывает, как обогнать бинарный поиск в отсортированных массивах 16-битных целых чисел размером до 4096 элементов с помощью гибридного алгоритма SIMD Quad.
Идея: разбить массив на блоки по 16 элементов, выполнить четвертичный интерполяционный поиск по последним элементам блоков, чтобы быстро определить нужный блок, а затем загрузить все 16 элементов блока в SIMD-регистры и проверить их параллельно одной инструкцией: SSE2 на Intel, NEON на ARM.
На Intel платформе алгоритм оказался более чем в 2 раза быстрее бинарного поиска на тёплом кэше, на Apple M4 — более чем в 2 раза быстрее на холодном
