جستجوی دودویی یکپارچه

(Uniform binary search) یک الگوریتم بهینه سازی کلاسیک جستوی باینری (binary search) است که توسط Donald Knuth اختراع شد وبا توجه به Knuth's The Art of Computer Programming. اون استفاده می کند از یک جدول مراجعه ی برای تغییر یک ارایه ذخیره شده.به جای گرفتن نقطه‌ی وسط کران بالا و پایین هر تکرار،بنابراین این اساس الگوریتم ساختاری ماننده (Knuth's MIX) را بهینه می‌کند.
1. جدول مراجعه‌ای به صورت عملا از جدول جمع و تغییر (addition and a shift) سریع‌تر است ، و
2.خیلی از جستجو‌ها ر یک آرایه انجام می‌شود،یا در چند آرایه با اندازه‌های برابر اجرا توسط C

یک الگوریتم جستجوی باینری یک سان مانند این،زمانی که توسط C اجرا می‌شود.

C implementation

#define LOG_N 42

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