Recherche séquentielle

Recherche linéaire

La recherche linéaire parcourt la séquence élément par élément, sans exploiter de structure particulière.

int linear_search(int *arr, int n, int x) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == x)
            return i; // trouvé
    }
    return -1; // non trouvé
}

Complexité :

  • Temps : $O(n)$ (meilleur cas $O(1)$ si trouvé en première position).
  • Mémoire : $O(1)$.
  • Sur un tableau contigu, la localité cache est bonne : les éléments sont chargés par blocs (cache lines) successifs.

Dans un modèle réaliste (RAM + hiérarchie de caches), le coût est dominé par le nombre de cache misses. Sur un tableau dense, une recherche linéaire peut être souvent plus rapide qu’un algorithme asymptotiquement meilleur, tant que $n$ reste dans le cache L2/L3.

Recherche dichotomique

La recherche dichotomique (binary search) exploite la structure d’un tableau trié pour éliminer la moitié de l’intervalle restant à chaque étape.

int binary_search(int *arr, int n, int x) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        if (x < arr[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

Justification asymptotique :

  • À chaque comparaison, la taille $n_k$ de l’intervalle de recherche vérifie $n_{k+1} = n_k / 2$.
  • Après $k$ itérations, $n_k = n / 2^k$.
  • On s’arrête lorsque $n_k \approx 1$, donc $n / 2^k \approx 1$ → $k \approx \log_2 n$.
  • Complexité en temps : $O(\log n)$, mémoire $O(1)$.

Binary search nécessite un accès aléatoire en $O(1)$. Sur une liste chaînée, l’accès à l’élément de milieu coûte déjà $O(n)$, ce qui détruit l’intérêt de la dichotomie. Ce n’est donc raisonnable que pour les structures contiguës (tableaux, vecteurs).

Dans la plupart des bibliothèques standard (C++, Rust, etc.), les fonctions de recherche dichotomique sont implémentées avec un soin particulier pour éviter les dépassements d’entier dans le calcul de mid et pour optimiser les branches (branch prediction).

Recherche par interpolation

La recherche par interpolation raffine la dichotomie en exploitant une hypothèse sur la distribution des données : si les valeurs sont à peu près uniformément réparties, la position de la clé peut être estimée par interpolation affine.

Formule :

$$
pos = left + \frac{(x - arr[left])}{(arr[right] - arr[left])} \times (right - left)
$$

int interpolation_search(int *arr, int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right && x >= arr[left] && x <= arr[right]) {
        if (left == right) {
            return arr[left] == x ? left : -1;
        }
        int pos = left + (int)((double)(right - left) *
                               (x - arr[left]) /
                               (arr[right] - arr[left]));
        if (arr[pos] == x)
            return pos;
        if (arr[pos] < x)
            left = pos + 1;
        else
            right = pos - 1;
    }
    return -1;
}

Analyse :

  • Si les données sont parfaitement uniformes, chaque interpolation réduit l’intervalle beaucoup plus vite qu’une bisection pure.
  • Complexité moyenne : $O(\log \log n)$.
  • Pire cas : si la distribution est pathologique (forte concentration d’éléments à une extrémité), la formule choisit systématiquement de « mauvaises » positions → $O(n)$.

L’intérêt réel de l’interpolation search est limité en pratique. Sur matériel moderne, le coût supplémentaire des divisions et conversions flottantes, combiné au risque de cas dégénérés, fait souvent préférer une dichotomie classique, plus stable et plus simple à analyser.

Tables de hachage

Les tables de hachage modélisent une fonction application $h : \mathcal{K} \to \{0, \dots, m-1\}$, où $\mathcal{K}$ est l’ensemble des clés et $m$ la taille du tableau. L’hypothèse fondamentale (souvent implicite) dans les analyses amorties est celle de hashage uniforme : chaque clé est envoyée de manière pseudo-aléatoire et uniforme dans les $m$ cases.

Chaining (chaînage séparé)

Chaque case du tableau est un bucket contenant une structure (souvent une liste chaînée) de toutes les paires (clé, valeur) qui y tombent.

struct entry {
    int key;
    int value;
    struct entry *next;
};

struct hash_table {
    struct entry **buckets;
    int m; // taille
};
  • Insertion : $i = h(key)$, on ajoute en tête de buckets[i].
  • Recherche : $i = h(key)$, on parcourt la liste en comparant key.

Analyse via facteur de charge :

  • On note $n$ le nombre total de clés insérées et $m$ la taille du tableau.
  • Le facteur de charge $\alpha = n / m$ mesure la longueur moyenne d’une liste.
  • Sous l’hypothèse de hashage uniforme, la longueur de la liste pour une case donnée suit approximativement une loi de Poisson de paramètre $\alpha$.
  • Temps moyen pour une recherche : $O(1 + \alpha)$.
  • Si $\alpha$ est borné (par exemple $\alpha \leq 1$), on a un temps moyen strictement constant.
  • Pire cas (toutes les clés dans le même bucket) : $O(n)$.

Pour des analyses plus fines, on peut montrer que la probabilité qu’un bucket dépasse une taille $k$ décroît de manière exponentielle en $k$, si la fonction de hash se comporte comme une fonction aléatoire. Cela justifie l’assertion « $O(1)$ amorti » dans les textes classiques.

Open addressing

L’open addressing stocke tous les éléments directement dans le tableau principal. En cas de collision, on suit une séquence de sondage.

Exemple : linear probing :

$$
h_0(k) = h(k),\quad h_{i+1}(k) = (h_i(k) + 1) \mod m
$$

#define EMPTY   0x7fffffff
#define DELETED 0x7ffffffe

int hash_insert(int *table, int m, int key) {
    int idx = key % m;
    for (int i = 0; i < m; ++i) {
        int j = (idx + i) % m;
        if (table[j] == EMPTY || table[j] == DELETED) {
            table[j] = key;
            return j;
        }
    }
    return -1; // table pleine
}

int hash_search(int *table, int m, int key) {
    int idx = key % m;
    for (int i = 0; i < m; ++i) {
        int j = (idx + i) % m;
        if (table[j] == EMPTY)
            return -1; // absent
        if (table[j] == key)
            return j;
    }
    return -1;
}

Complexité :

  • Sous hashage uniforme, temps moyen de recherche $O(1)$ tant que le facteur de charge $\alpha = n / m$ reste raisonnable (typiquement $\alpha < 0.7$).
  • Plus $\alpha$ se rapproche de 1, plus les séquences de sondage s’allongent (phénomène de clustering).
  • Pire cas : tableau saturé ou série de collisions pathologiques → $O(n)$.

La suppression est délicate : si l’on met simplement la case à EMPTY, on casse la séquence de sondage et certaines clés deviennent inaccessibles. On doit utiliser un marqueur spécial DELETED, ce qui ajoute de la complexité conceptuelle et nécessite des passes de « nettoyage » ou un rehash périodique.

Sur le plan cache, l’open addressing est très performant : toutes les sondes restent dans un tableau contigu, ce qui maximise les cache hits. À l’inverse, le chaining multiplie les accès indirects en mémoire (pointeurs) et souffre de cache misses, malgré une meilleure résilience aux facteurs de charge élevés.

Synthèse : quand utiliser quoi ?

Problème Structure / Algo Temps typique Remarques principales
Recherche dans tableau non trié Recherche linéaire $O(n)$ Simple, bon pour petits $n$
Recherche dans tableau trié Binary search $O(\log n)$ Nécessite structure contiguë
Tableau trié + distribution uniforme Interpolation search $O(\log \log n)$ moy. Sensible aux distributions pathologiques
Mapping clé/valeur (général) Hash table $O(1)$ moy. Hypothèse de hashage uniforme

En pratique :

  • Tableaux + binary search dominent dans les cas où la structure est majoritairement statique (beaucoup de lectures, peu d’écritures).
  • Tables de hachage dominent pour les dictionnaires dynamiques à accès exact, avec de nombreuses insertions/suppressions.