Recherche binaire uniforme - Uniform binary search

La recherche binaire uniforme est une optimisation de l' algorithme de recherche binaire classique inventé par Donald Knuth et donné dans The Art of Computer Programming de Knuth . Il utilise une table de recherche pour mettre à jour un seul index de tableau, plutôt que de prendre le milieu d'une limite supérieure et inférieure à chaque itération; par conséquent, il est optimisé pour les architectures (telles que Knuth's MIX ) sur lesquelles

  • une recherche de table est généralement plus rapide qu'un ajout et un décalage, et
  • de nombreuses recherches seront effectuées sur le même tableau, ou sur plusieurs tableaux de même longueur

Implémentation C

L'uniforme algorithme de recherche binaire ressemble à ceci, lorsque mis en œuvre en 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 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;
}

Les références

Liens externes