# 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 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 i, a[N] = {1,3,5,6,7,9,14,15,17,19};
make_delta(N);
for (i=0; i < 20; ++i)
printf("%d is at index %d\n", i, unisearch(a, i));
return 0;
}
```