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.