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

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

    پیوند به بیرون

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.