Единый двоичный поиск - Uniform binary search

Единый двоичный поиск это оптимизация классического бинарный поиск алгоритм изобретен Дональд Кнут и дано в книге Кнута Искусство программирования. Он использует Справочная таблица обновлять единичный индекс массива, а не брать среднюю точку верхней и нижней границ на каждой итерации; поэтому он оптимизирован для архитектур (таких как Knuth's СМЕШИВАНИЕ ) на котором

  • поиск в таблице обычно выполняется быстрее, чем сложение и сдвиг, и
  • много поисков будет выполняться в одном массиве или в нескольких массивах одинаковой длины

C реализация

Униформа алгоритм двоичного поиска выглядит так, когда реализовано в C.

#define LOG_N 4статический int дельта[LOG_N];пустота make_delta(int N){    int мощность = 1;    int я = 0;    делать {        int половина = мощность;        мощность <<= 1;        дельта[я] = (N + половина) / мощность;    } пока (дельта[я++] != 0);}int unisearch(int *а, int ключ){    int я = дельта[0] - 1;  / * середина массива * /    int d = 0;    пока (1) {        если (ключ == а[я]) {            возвращаться я;        } еще если (дельта[d] == 0) {            возвращаться -1;        } еще {            если (ключ < а[я]) {                я -= дельта[++d];            } еще {                я += дельта[++d];            }        }    }}/ * Пример использования: * /#define N 10int главный(пустота){    int а[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19};    make_delta(N);    за (int я = 0; я < 20; ++я)        printf("% d находится в индексе% d", я, unisearch(а, я));    возвращаться 0;}

Рекомендации

внешняя ссылка