Uniform binary search: Difference between revisions

Revision as of 05:27, 20 February 2018

Revision as of 13:28, 17 December 2019

Line 7:

The uniform [[binary search algorithm]] looks like this, when implemented in [[C (programming language)|C]].

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

<source lang="c">

#define LOG_N 4

static int delta[LOG_N];

#define LOG_N 4

void make_delta(int N)

static int delta[LOG_N];

{

int power = 1;

void make_delta(int N)

int returni = 0;

{

do int power = 1;{

int ihalf = 0power;

do { power <<= 1;

delta[i] int= (N + half) =/ power;

} while (delta[i++] power <<!= 10);

}

delta[i] = (N + half) / power;

} while (delta[i++] != 0);

int unisearch(int *a, int key)

}

{

int i = delta[0]-1; /* midpoint of array */

int unisearch(int *a, int key)

int d = }0;

{

int i = delta[0]-1; /* midpoint of array */

while int(1) d = 0;{

if (key == a[i]) {

while (1) { return i;

} else if (keydelta[d] == a[i]0) {

return i-1;

} else if (delta[d] == 0) {

if return(key -1;< a[i]) {

} else { i -= delta[++d];

} if (key < a[i])else {

i -+= delta[++d];

} else {

i += delta[++d];}

}

}

}

}

/* Example of use: */

}

#define N 10

int main(void)

/* Example of use: */

{

#define N 10

int i, a[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19};

int main(void)

make_delta(N);

{

for (i=0; i < 20; ++i)

int i, a[N] = {1,3,5,6,7,9,14,15,17,19};

printf("%d is at index %d\n", i, unisearch(a, i));

make_delta(N);

return for (i=0; i < 20; ++i)

}

printf("%d is at index %d\n", i, unisearch(a, i));

</source>

return 0;

}

==References==