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;
        }
        if (delta[d] == 0) {
          return -1;
        }
        if (key < a[i]) {
          i -= delta[d++];
        }
        else {
          i += delta[d++];
        }
    }
}

void main(void)
{
  int searchArray[] = { 0, 2, 5, 9, 11, 15, 
                        22, 24, 25, 29, 30, 31, 
                        40, 45, 50, 55, 60 };
  int saSize = sizeof(searchArray) / sizeof(searchArray[0]);
  printf("saSize: %d\n", saSize);
  make_delta(saSize - 2); // doesn't work unless subtract 2 ???
  int index = unisearch(searchArray, 29);
  index = unisearch(searchArray, 12);
  index = unisearch(searchArray, 9);
  index = unisearch(searchArray, 30);
  for (int key = 0; key < 66; key += 3) {
    index = unisearch(searchArray, key);
    printf("Index: %-2d  Key: %-2d  Value: %-2d\n", 
        index, key, searchArray[index]);
  }
}

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}.

--Lynn 07:52, 24 June 2006 (UTC)

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