समान द्विभाजी अन्वेषण

समान द्विभाजी अन्वेषण, डोनाल्ड नुथ द्वारा आविष्कृत और नुथ की कंप्यूटर प्रोग्रामिंग की कला में दिए गए उत्कृष्ट द्विभाजी अन्वेषण कलन विधि का एक अनुकूलन है। यह प्रत्येक पुनरावृत्ति पर ऊपरी और निचली सीमा के मध्यबिंदु को लेने के बदले, एकल सरणी सूचकांक को अद्यतन करने के लिए एक लुकअप टेबल का उपयोग करता है; इसलिए, इसे संरचना (जैसे नथ के मिश्रण) के लिए अनुकूलित किया गया है।

• एक टेबल लुकअप सामान्यतः एक जोड़ और शिफ्ट से तेज़ होता है, और
• कई खोज एक ही सरणी पर, या एक ही लंबाई की कई सरणियों पर की जाएंगी

C कार्यान्वयन

C (प्रोग्रामिंग भाषा) में उपयोजित होने पर एकसमान द्विभाजी अन्वेषण कलन विधि इस प्रकार दिखती है।

#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;
}

संदर्भ

• Knuth. The Art of Computer Programming, Volume 3. Page 412, Algorithm C.

बाहरी संबंध

• An implementation of Knuth's algorithm in Pascal, by Han de Bruijn
• An implementation of Knuth's algorithm in Go, by Adrianus Warmenhoven