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
The uniform binary search algorithm looks like this, when implemented in C.
#define LOG_N 4staticintdelta[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 10intmain(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;}