Uniform binary search: Difference between revisions

Revision as of 01:58, 28 April 2006

Revision as of 07:52, 24 June 2006

Line 35:

while (1) {

if (key == a[i]) return{ i;

else if (delta[d] == 0) return -1i;

}

if else i += (delta[d++]; == 0) {

return -1;

}

if (key < a[i]) {

i -= delta[d++];

}

else {

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]);

}

}

Line 47 ⟶ 72:

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)

==References==