Uniform_binary_search Knowpia

Uniform binary search is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth's The Art of Computer Programming. It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a lower bound on each iteration; therefore, it is optimized for architectures (such as Knuth's MIX) on which

a table lookup is generally faster than an addition and a shift, and
many searches will be performed on the same array, or on several arrays of the same length

C implementation edit

The uniform binary search algorithm looks like this, when implemented in 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;
}

References edit

Knuth. The Art of Computer Programming, Volume 3. Page 412, Algorithm C.

External links edit

An implementation of Knuth's algorithm in Pascal, by Han de Bruijn
An implementation of Knuth's algorithm in Go, by Adrianus Warmenhoven

Summary

C implementation edit

References edit

External links edit