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

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

• एक टेबल लुकअप आम तौर पर एक जोड़ और एक बदलाव से तेज़ होता है, और
• कई खोजें एक ही सारणी पर, या एक ही लंबाई की कई सारणियों पर की जाएंगी

सी कार्यान्वयन

सी (प्रोग्रामिंग भाषा) में लागू होने पर एकसमान बाइनरी खोज एल्गोरिदम इस तरह दिखता है।

#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