Uniform binary search

Uniform binary search is an optimization of the classic binary search algorithm. It was first published by Donald Knuth, in The Art of Computer Programming , who credited its idea to Ashok K. Chandra.^[1] 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

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

#define LOG_N 4
staticintdelta[LOG_N];
voidmake_delta(intN)
{
intpower=1;
inti=0;
do{
inthalf=power;
power<<=1;
delta[i]=(N+half)/power;
}while(delta[i++]!=0);
}
intunisearch(int*a,intkey)
{
inti=delta[0]-1;/* midpoint of array */
intd=0;
while(1){
if(key==a[i]){
returni;
}elseif(delta[d]==0){
return-1;
}else{
if(key<a[i]){
i-=delta[++d];
}else{
i+=delta[++d];
}
}
}
}
/* Example of use: */
#define N 10
intmain(void)
{
inta[N]={1,3,5,6,7,9,14,15,17,19};
make_delta(N);
for(inti=0;i<20;++i)
printf("%d is at index %d\n",i,unisearch(a,i));
return0;
}

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

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

• Search algorithms

• Articles with example C code