Recherche dichotomique
Dernière mise à jour
La recherche dichotomique (ou recherche binaire) trouve une valeur cible dans un tableau **trié** en divisant la fenêtre de recherche par deux à chaque étape. Elle compare l'élément du milieu à la cible : en cas d'égalité, la recherche se termine ; sinon, la moitié qui ne peut pas contenir la cible est écartée et la fenêtre se réduit à l'autre moitié. Chaque comparaison élimine la moitié des éléments restants, c'est pourquoi elle s'exécute en O(log n) — chercher parmi un million de valeurs triées demande au plus une vingtaine de comparaisons.
L'animation ci-dessus montre les pointeurs lo, mid et hi et estompe la moitié éliminée après chaque comparaison. La seule précondition non négociable : le tableau doit déjà être trié — sur des données non triées, il faut la recherche linéaire ou d'abord un tri (voir le tri fusion). La même idée de division par deux est au cœur de l'arbre binaire de recherche.
Complexité en temps et en espace
| Cas | Complexité | Remarques |
|---|---|---|
| Meilleur cas | O(1) | L'élément du milieu est la cible dès la première comparaison. |
| Cas moyen | O(log n) | Chaque comparaison divise par deux la fenêtre restante. |
| Pire cas | O(log n) | La fenêtre se réduit à un seul élément avant de trouver ou d'échouer. |
| Espace | O(1) | La version itérative ne conserve que les indices lo, hi et mid. |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Initialisez lo au premier indice et hi au dernier indice du tableau trié. |
| 2 | Calculez l'indice du milieu : mid = (lo + hi) // 2. |
| 3 | Si a[mid] est égal à la cible, renvoyez mid — trouvé. |
| 4 | Si a[mid] est **inférieur** à la cible, la cible ne peut être que dans la moitié droite : posez lo = mid + 1. |
| 5 | Si a[mid] est **supérieur** à la cible, cherchez dans la moitié gauche : posez hi = mid - 1. |
| 6 | Répétez à partir de l'étape 2 tant que lo <= hi ; si la fenêtre se vide, la cible n'est pas dans le tableau. |
Exemple détaillé
Recherche de 5 dans [1, 2, 3, 5, 7, 8, 9] :
| Passage | Fenêtre (lo..hi) | mid | a[mid] | Action |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — cible trouvée à l'indice 3. |
Un échec, étape par étape
Chercher 4 dans le même tableau montre comment la fenêtre se vide :
| Passage | Fenêtre (lo..hi) | mid | a[mid] | Action |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — cherchez dans la moitié gauche, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4 — cherchez dans la moitié droite, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo devient 3, la fenêtre se vide : introuvable. |
Quand utiliser la recherche dichotomique
| À utiliser quand | À éviter quand |
|---|---|
| Les données sont déjà triées (ou vous y cherchez de nombreuses fois) | Les données ne sont pas triées et ne sont cherchées qu'une seule fois — trier d'abord coûte O(n log n) |
| La collection permet un accès direct rapide (tableaux) | Vous n'avez qu'un accès séquentiel (listes chaînées) |
Le jeu de données est grand — O(log n) brille à grande échelle | Le jeu de données est minuscule — un simple parcours est tout aussi rapide et plus simple |
Code de Binary Search
Une implémentation propre et exécutable de Binary Search en Python, JavaScript, Java, C++, C, Pseudocode. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Binary Search en Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Code de Binary Search en JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Code de Binary Search en Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Code de Binary Search en C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Code de Binary Search en C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Code de Binary Search en Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)FAQ sur la recherche dichotomique
Quelle est la complexité en temps de la recherche dichotomique ?
O(log n) dans les cas moyen et pire, car chaque comparaison divise par deux la fenêtre de recherche restante, et O(1) dans le meilleur cas, quand le premier élément du milieu est la cible. La version itérative utilise O(1) d'espace supplémentaire.Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?
L'étape de division par deux repose sur l'ordre : comparer la cible à l'élément du milieu n'indique quelle moitié écarter que si tout ce qui est à gauche du milieu est plus petit et tout ce qui est à droite est plus grand. Sur des données non triées, cette déduction n'est pas valable — utilisez plutôt la recherche linéaire, ou triez d'abord.
Quelle est la différence entre la recherche dichotomique et la recherche linéaire ?
La recherche linéaire parcourt les éléments un par un (
O(n)) et fonctionne sur n'importe quel tableau ; la recherche dichotomique divise par deux la fenêtre de recherche d'un tableau trié (O(log n)) mais exige une entrée triée. Pour une poignée d'éléments, la différence est négligeable — à grande échelle, la recherche dichotomique l'emporte nettement.Combien de comparaisons la recherche dichotomique nécessite-t-elle ?
Au plus environ
log2(n) + 1 : 10 comparaisons couvrent 1 000 éléments, 20 comparaisons en couvrent 1 000 000. Cette croissance logarithmique en fait la recherche par défaut sur des données triées.Quel est le célèbre bug de dépassement dans la recherche dichotomique ?
Calculer le milieu avec
(lo + hi) / 2 peut faire déborder des entiers de taille fixe lorsque lo + hi dépasse le maximum du type. La forme sûre est mid = lo + (hi - lo) / 2. En Python cela n'a pas d'importance (entiers à précision arbitraire), mais en Java/C/C++ c'est un bug réel et célèbre.La recherche dichotomique est-elle la même chose qu'un arbre binaire de recherche ?
Ils partagent l'idée de division par deux mais diffèrent par leur structure : la recherche dichotomique est un algorithme sur un tableau trié, tandis qu'un arbre binaire de recherche est une structure de données chaînée qui garde ses clés ordonnées, de sorte que les recherches descendent à gauche ou à droite à chaque nœud.
Ressources associées
Plus de visualisations
