Uniform binary search: Difference between revisions

Revision as of 02:50, 27 September 2006

Revision as of 06:30, 27 September 2006

Line 3:

*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 programming language|C]].

<!-- Please don't break this code. Test before editing! -->

#define LOG_N 42

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;

}

==References==