La recherche dichotomique expliquée simplement
Un tutoriel complet pour comprendre la recherche dichotomique, savoir quand l'utiliser et l'implémenter pas à pas en JavaScript.
La recherche dichotomique
Introduction
La recherche dichotomique est l'un des algorithmes les plus utiles à connaître.
Son principe est simple : au lieu de parcourir toute une liste, on coupe l'espace de recherche en deux à chaque étape.
C'est beaucoup plus efficace qu'une recherche classique, mais à une condition importante : la liste doit être triée.
Ce que vous allez apprendre
À la fin de ce tutoriel, vous saurez :
- comprendre le principe de la recherche dichotomique ;
- savoir quand l'utiliser ;
- savoir pourquoi la liste doit être triée ;
- écrire l'algorithme en JavaScript ;
- gérer les cas limites ;
- comparer cette approche à une recherche simple.
1. Le problème de départ
Imaginons une liste de nombres triée :
const numbers = [2, 4, 7, 10, 15, 18, 21, 30];
Si vous cherchez 18, vous pourriez commencer au début et vérifier chaque élément un par un.
Mais si la liste est triée, il existe une meilleure méthode.
2. L'idée de la recherche dichotomique
La recherche dichotomique fonctionne ainsi :
- on regarde l'élément au milieu ;
- si c'est la valeur cherchée, on s'arrête ;
- sinon, on sait dans quelle moitié continuer ;
- on recommence sur cette moitié ;
- on répète jusqu'à trouver la valeur ou jusqu'à ce qu'il n'y ait plus rien à chercher.
C'est une stratégie de division par deux.
3. Pourquoi c'est plus rapide ?
À chaque étape, on élimine la moitié des éléments restants.
Sur une petite liste, la différence n'est pas toujours visible.
Sur une grande liste, le gain devient important.
Par exemple :
- une recherche linéaire peut vérifier un élément après l'autre ;
- une recherche dichotomique réduit très vite le nombre de comparaisons.
4. La condition essentielle
La recherche dichotomique ne fonctionne correctement que si la liste est triée.
Pourquoi ?
Parce que l'algorithme décide dans quelle moitié continuer en se basant sur l'ordre des valeurs.
Sans tri, cette décision serait fausse.
5. Exemple pas à pas
Cherchons 18 dans cette liste :
const numbers = [2, 4, 7, 10, 15, 18, 21, 30];
Première étape
On regarde le milieu.
La valeur centrale n'est pas 18, mais on compare pour savoir de quel côté continuer.
Deuxième étape
On se concentre sur la moitié qui contient potentiellement 18.
Troisième étape
On recommence jusqu'à trouver la valeur.
C'est cette logique qui rend l'algorithme élégant et efficace.
6. Version JavaScript simple
Voici une implémentation claire de la recherche dichotomique :
function binarySearch(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (array[middle] === target) {
return middle;
}
if (array[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
Comment lire ce code ?
leftreprésente le début de la zone de recherche ;rightreprésente la fin de la zone de recherche ;middleest l'index du milieu ;- si la valeur du milieu est plus petite que la cible, on cherche à droite ;
- sinon, on cherche à gauche.
7. Exemple d'utilisation
const numbers = [2, 4, 7, 10, 15, 18, 21, 30];
console.log(binarySearch(numbers, 18)); // 5
console.log(binarySearch(numbers, 9)); // -1
La fonction retourne :
- l'index de l'élément si la valeur est trouvée ;
-1si elle n'existe pas.
8. Le rôle de la boucle while
La boucle while permet de continuer tant que la zone de recherche est valide.
while (left <= right) {
// continuer à chercher
}
Quand left devient plus grand que right, cela signifie qu'il n'y a plus d'élément à tester.
9. Les cas limites à vérifier
Liste vide
binarySearch([], 10);
Le résultat doit être -1.
Un seul élément
binarySearch([10], 10);
Le résultat doit être 0.
Valeur absente
binarySearch([1, 2, 3, 4], 8);
Le résultat doit être -1.
Valeur répétée
Si la valeur apparaît plusieurs fois, cette version renvoie l'un des indices trouvés, pas forcément le premier.
10. Recherche linéaire ou dichotomique ?
Recherche linéaire
Elle passe sur chaque élément un par un.
Elle est plus simple à écrire, mais moins efficace sur de grandes listes.
Recherche dichotomique
Elle est plus rapide, mais nécessite une liste triée.
Le choix dépend donc du contexte.
11. Erreurs fréquentes
Oublier de trier la liste
Si la liste n'est pas triée, la recherche dichotomique donne un résultat incorrect.
Mal gérer les bornes
Une erreur sur left ou right peut casser tout l'algorithme.
Oublier le cas "non trouvé"
La fonction doit toujours retourner quelque chose de clair quand la valeur n'existe pas.
12. Résumé
La recherche dichotomique est un algorithme puissant pour retrouver une valeur dans une liste triée.
À retenir :
- la liste doit être triée ;
- on coupe l'espace de recherche en deux à chaque étape ;
- l'algorithme est rapide et très utilisé ;
- il faut bien gérer les bornes et le cas où la valeur n'existe pas.
Exercices
Exercice 1
Implémentez la recherche dichotomique sur une liste de nombres triée.
Exercice 2
Testez votre fonction avec une valeur présente et une valeur absente.
Exercice 3
Modifiez la fonction pour qu'elle retourne true ou false au lieu de l'index.
Exercice 4
Essayez avec une liste vide.
Corrigés
Correction exercice 1
function binarySearch(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (array[middle] === target) {
return middle;
}
if (array[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
Correction exercice 3
function contains(array, target) {
return binarySearch(array, target) !== -1;
}
Prochaine étape
Une fois la recherche dichotomique comprise, il est naturel d'étudier les algorithmes de tri, car ils utilisent une logique très complémentaire.