Üniforma ikili arama - Uniform binary search

Üniforma ikili arama klasik bir optimizasyon ikili arama tarafından icat algoritması Donald Knuth ve Knuth'un verilen Bilgisayar Programcılığı Sanatı . Bu kullanan arama tablosu yerine bir üst ve her tekrarında bir alt sınır orta noktası alarak daha, tek bir dizi indeksi güncelleştirmek için; bu nedenle, (örneğin, Knuth olarak mimariler için optimize edilmiştir MIX üzerine)

• Bir tablo arama bir ekleme ve bir kayma genellikle daha hızlıdır ve
• Birçok arama aynı dizi üzerinde gerçekleştirilir, veya aynı uzunlukta birçok diziler üzerinde olacak

C uygulaması

Üniforma ikili arama algoritması uygulanan zaman, şuna benzer 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 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;
}

Referanslar

• Knuth . Bilgisayar Programlama Sanatı , Cilt 3. sayfa 412, Algoritma C

Dış bağlantılar

• Knuth'un algoritmanın bir uygulama içinde Pascal Han de Bruijn tarafından,
• Knuth'un algoritmanın bir uygulama içinde git tarafından, Adrianus Warmenhoven