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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

(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.

پیوند به بیرون[ویرایش]