Talk:Uniform binary search

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) Note that this code has a tough time with arrays that have an even number of elements ... I found you need to put 'sentinel' entries that are max-value at the end. I suspect the code wasn't translated quite right from the original MIX code in Dr. Knuth's book.