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 = milieusans+ 1, ou d'un mauvais choix de condition d'arrêt.
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.