Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › La recherche binaire et ses pièges

La recherche binaire et ses pièges

Tri, recherche et Streamsintermediaire

La recherche binaire divise l'intervalle par deux à chaque étape : O(log n). Encore faut-il l'écrire sans bug.

La version qui trouve l'égalité :

static int chercher(int[] trie, int cible) {
    int bas = 0, haut = trie.length - 1;
    while (bas <= haut) {                       // <= : intervalle fermé [bas, haut]
        int m = bas + (haut - bas) / 2;         // jamais (bas + haut) / 2
        if (trie[m] == cible) return m;
        if (trie[m] < cible) bas = m + 1;       // + 1 : indispensable
        else haut = m - 1;
    }
    return -1;
}

La version la plus utile en pratique — la borne inférieure, « première position où insérer » :

static int borneInferieure(int[] trie, int cible) {
    int bas = 0, haut = trie.length;            // intervalle semi-ouvert [bas, haut[
    while (bas < haut) {
        int m = bas + (haut - bas) / 2;
        if (trie[m] < cible) bas = m + 1;
        else haut = m;                           // on garde m comme candidat
    }
    return bas;                                  // premier index avec trie[index] >= cible
}

Elle répond à « premier élément ≥ x », « combien d'éléments < x », « où insérer » — des questions bien plus fréquentes que l'égalité stricte.

Les trois pièges, tous rencontrés en entretien : le débordement de (bas + haut) / 2, le + 1 manquant qui provoque une boucle infinie, et l'oubli que le tableau doit être trié.

Les termes à connaître

Recherche binaire

Chercher dans un ensemble trié en divisant l'intervalle par deux à chaque étape : O(log n). Vingt étapes suffisent pour un million d'éléments.

Invariant de recherche

« Si la cible existe, elle est dans [bas, haut] ». Chaque itération doit préserver cette propriété — c'est ce qui rend l'algorithme correct.

Borne inférieure (*lower bound*)

La première position où insérer la cible sans casser l'ordre. Répond à « premier élément ≥ x », plus utile que la recherche d'égalité stricte.

Arrays.binarySearch

L'implémentation du JDK. Renvoie l'index si trouvé, sinon -(point d'insertion) - 1 — une valeur négative qu'il faut savoir décoder.

Recherche binaire sur la réponse

Quand la réponse est un nombre et qu'une fonction « ce candidat suffit-il ? » est monotone, on dichotomie sur la valeur plutôt que sur un tableau.

Boucle infinie

Le bug classique : un intervalle qui ne se réduit pas. Il vient d'un bas = milieu sans + 1, ou d'un mauvais choix de condition d'arrêt.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.