Единый двоичный поиск

Равномерный двоичный поиск — это оптимизация классического алгоритма двоичного поиска , изобретенного Дональдом Кнутом и приведенного в книге Кнута « Искусство компьютерного программирования» . Он использует таблицу поиска для обновления одного индекса массива, а не берет среднюю точку верхней и нижней границы на каждой итерации; Кнута поэтому он оптимизирован для архитектур (таких как MIX ), на которых

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

Реализация на языке C

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

#define LOG_N 4

static int delta[LOG_N];

void make_delta(int N)
{
    int power = 1;
    int i = 0;

    do {
        int half = power;
        power <<= 1;
        delta[i] = (N + half) / power;
    } while (delta[i++] != 0);
}

int unisearch(int *a, int key)
{
    int i = delta[0] - 1;  /* midpoint of array */
    int d = 0;

    while (1) {
        if (key == a[i]) {
            return i;
        } else if (delta[d] == 0) {
            return -1;
        } else {
            if (key < a[i]) {
                i -= delta[++d];
            } else {
                i += delta[++d];
            }
        }
    }
}

/* Example of use: */
#define N 10

int main(void)
{
    int a[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19};

    make_delta(N);

    for (int i = 0; i < 20; ++i)
        printf("%d is at index %d\n", i, unisearch(a, i));

    return 0;
}

Ссылки

• Кнут . Искусство компьютерного программирования , Том 3. Страница 412, Алгоритм C.

Внешние ссылки

• Реализация алгоритма Кнута на языке Паскаль , автор Хан де Брейн.
• Реализация алгоритма Кнута в Go , автор Адрианус Варменховен.