Uniform binary search

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

The uniform binary search algorithm looks like this, when implemented in C:

#define LOG_N 42

static int delta[LOG_N];

void make_delta(int N)
{
    int lgN, power;
    int i;

    lgN = 0;
    for (i = N; i > 0; i >>= 1)
      ++lgN;

    power = 1;
    for (i=0; i <= lgN; ++i) {
        int half = power;
        power <<= 1;
        delta[i] = (N + half) / power;
    }
}

int unisearch(int *a, int key)
{
    int i = delta[0];  /* 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++];
        }
    }
}

The programmer is expected to call make_delta(N) before attempting to use unisearch(a, x) on any array a with length N, and re-invoke make_delta before any call to unisearch(b, x) in which b has a different number of elements from a.

The make_delta function initializes the array delta with successive halvings of N, rounded up; for example, if N=40, then delta will be initialized to {20, 10, 5, 3, 1, 1, 0}.

References

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

External link

• An implementation of Knuth's algorithm in Pascal, by Han de Bruijn