Uniform binary search

<h2 id="c-implementation">C implementation</h2>
<p>The uniform <a href="/facts/Binary_search_algorithm/FFmQzunc">binary search algorithm</a> looks like this, when implemented in <a href="/facts/C_(programming_language)/Ky2No763">C</a>.
</p>
#define LOG_N 4

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 a[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19};

make_delta(N);

for (int i = 0; i < 20; ++i)
        printf("%d is at index %d\n", i, unisearch(a, i));

return 0;
}

<ul><li><a href="/facts/Donald_Knuth/GozNzDM6">Knuth</a>. <i><a href="/facts/The_Art_of_Computer_Programming/MR1bMD9e">The Art of Computer Programming</a></i>, Volume 3. Page 412, Algorithm C.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://github.com/adrianuswarmenhoven/uniformbinarysearch_go/blob/master/Pascal/unizoek.pas">An implementation of Knuth's algorithm</a> in <a href="/facts/Pascal_(programming_language)/b3yvp8bF">Pascal</a>, by Han de Bruijn</li>
<li><a href="https://github.com/adrianuswarmenhoven/uniformbinarysearch_go">An implementation of Knuth's algorithm</a> in <a href="/facts/Go_(programming_language)/oWlsmAFJ">Go</a>, by Adrianus Warmenhoven</li></ul>

Uniform binary search open-in-new

Uniform binary search