|
*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 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 <code>make_delta(N)</code> before attempting to use <code>unisearch(a, x)</code> on any array <code>a</code> with length <code>N</code>, and re-invoke <code>make_delta</code> before any call to <code>unisearch(b, x)</code> in which <code>b</code> has a different number of elements from <code>a</code>.
The <code>make_delta</code> function initializes the array <code>delta</code> with successive halvings of <code>N</code>, rounded up; for example, if <code>N=40</code>, then <code>delta</code> will be initialized to {20, 10, 5, 3, 1, 1, 0}.
--[[User:L d allan|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.
==References==
| 