Binary Search

La recherche dichotomique compare avec l'élément central d'un tableau trié et divise l'intervalle par deux à chaque étape, localisant une cible en O(log n) ; c'est l'algorithme de recherche efficace fondateur.

Objectif

Localiser efficacement des éléments dans des données triées, en appliquant une complexité logarithmique à la recherche.

Mécanisme

On maintient l'intervalle [lo, hi] avec mid=(lo+hi)/2 ; on compare mid à la cible : retour en cas d'égalité, recherche dans la moitié droite si plus petit, dans la moitié gauche si plus grand. L'intervalle est divisé par deux à chaque étape, d'où O(log n). Le tri est un prérequis. Variantes : borne inférieure, borne supérieure, point d'insertion.

Cas d’usage

Recherche dans des tableaux triés
Index B+ tree de bases de données
Bisect dans le contrôle de versions
Recherche des zéros d'une fonction (dichotomie)

Exemples

entrée
```
Search 5 in [1,3,5,7,9]
```
Output
```
Index 2
```
2 comparisons

Erreurs courantes

lo+hi integer overflow: Use lo+(hi-lo)/2

Termes associés

Sorting Algorithm

Les algorithmes de tri arrangent les éléments en ordre — tri rapide, tri fusion et tri par tas sont courants — avec des complexités allant de O(n log n) à O(n²).

La notation grand O décrit la borne supérieure asymptotique d'une fonction, utilisée pour analyser la complexité temporelle/spatiale des algorithmes en ignorant les constantes et les termes d'ordre inférieur.

Une table de hachage associe des clés à un tableau de compartiments via une fonction de hachage, offrant recherche/insertion/suppression en O(1) en moyenne ; c'est l'une des structures de données les plus utilisées.

References