Recherche dichotomique
NSI Première
Définition
La recherche dichotomique (ou recherche binaire) est un algorithme qui localise une valeur dans un tableau trié en divisant à chaque étape l'intervalle de recherche par deux. On compare la cible à l'élément du milieu : si elle est plus petite on poursuit dans la moitié gauche, sinon dans la moitié droite. Sa complexité est logarithmique, bien plus efficace qu'une recherche séquentielle.
Formule
$$C(n) = O(\log_2 n) \qquad m = \left\lfloor \frac{g + d}{2} \right\rfloor$$
Exemple corrigé
Énoncé
Rechercher la valeur 23 dans le tableau trié `[3, 9, 14, 23, 31, 42, 55]` par dichotomie, en indiquant les indices visités.
Solution
Le tableau a 7 éléments (indices 0 à 6). On note `g` et `d` les bornes.
- Étape 1 : `g=0`, `d=6`, milieu `m = (0+6)//2 = 3`, `T[3] = 23` → trouvé.
La valeur est trouvée dès la première comparaison. Code général :
```python
def dichotomie(T, cible):
g, d = 0, len(T) - 1
while g <= d:
m = (g + d) // 2
if T[m] == cible:
return m
elif T[m] < cible:
g = m + 1
else:
d = m - 1
return -1
T = [3, 9, 14, 23, 31, 42, 55]
print(dichotomie(T, 23)) # 3
```
$\boxed{\text{indice } 3}$
Erreurs classiques
- Appliquer la dichotomie sur un tableau non trié : l'algorithme exige un tableau ordonné pour être correct.
- Mal mettre à jour les bornes (`g = m` au lieu de `g = m + 1`), ce qui provoque une boucle infinie.
Pour aller plus loin : le chapitre « Algorithmique » (cours et exercices corrigés).