NSI - Numérique et Sciences Informatiques
La recherche dichotomique

Prérequis au TD

Python : liste, parcours de listes.

Présentation de la méthode de recherche par dichotomie

La recherche dichotomique, (en anglais : binary search), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié.

Le principe est le suivant :

Trier le tableau de nombres ;
Comparer l'élément que l'on cherche avec la valeur de la case au milieu du tableau ;
- Si les valeurs sont égales, la tâche est accomplie,
- sinon on recommence dans la moitié du tableau pertinente.

Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.

Une introduction en vidéo de la recherche dichotomique

Vidéo : la recherche dichotomique.

Le TD/Cours de recherche par dichotomie

TD et cours : recherche par dichotomie.
Les exercices proposés sont à traiter sur repl ou via Capytal.

Remarque et compléments

Les algorithmes proposés peuvent s'avérer être faux dans certains langages

Calcul du terme médian
Le problème vient de l'addition des indices $a$ et $b$ pour en trouver calculer la moyenne. En général, $a$ et $b$ sont des pointeurs, des adresses mémoires. Et leur somme peut dépasser la taille de représentation des adresses. En effet, ce n'est pas parce que $a$ et $b$ sont représentables en 64 bits que $a+b$ l'est aussi. Il peut y avoir un dépassement.

Dans ce cas (qui peut arriver en pratique), le résultat obtenu en effectuant $(a+b)//2$ ne correspondra pas à la moyenne attendue.

Cette erreur est restée pendant plusieurs décennies dans divers bibliothèques (en Java, notamment) avant d'être détectée, (des compléments sur cette page).

Pour éviter cela, une version rigoureuse est

m = a + (b - a) // 2

En Python, cependant, on n'a pas ce problème (en Python3 du moins), car les entiers peuvent être arbitrairement grands.