Recherche binaire — algorithme, complexité temporelle et code

La recherche binaire est une méthode rapide pour trouver une cible dans une liste triée. On examine l’élément du milieu, on élimine la moitié des valeurs restantes, puis on recommence. Si la liste n’est pas ordonnée, cette logique ne tient plus.

Dans une liste triée par ordre croissant, la règle est simple : si la valeur du milieu est plus petite que la cible, on cherche à droite ; si elle est plus grande, on cherche à gauche. Comme l’intervalle est réduit d’environ moitié à chaque étape, la recherche binaire s’exécute en temps $O(\log n)$.

Comment fonctionne la recherche binaire sur une liste triée

Utilisez cette liste triée :

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Supposons que la cible soit $31$.

Commencez avec l’intervalle complet. La valeur du milieu est $24$. Comme $31 > 24$, tout ce qui se trouve à gauche de $24$ peut être écarté, donc la recherche continue dans

$$[31, 39, 45, 52]$$

Maintenant, la valeur du milieu est $39$. Comme $31 < 39$, tout ce qui se trouve à droite de $39$ peut être écarté, donc l’intervalle devient

$$[31]$$

Maintenant, la valeur du milieu est $31$, donc la recherche s’arrête. L’idée utile n’est pas seulement que la cible a été trouvée. En deux comparaisons, l’intervalle candidat est passé de $9$ valeurs à $1$.

Pourquoi la recherche binaire est en $O(\log n)$

Chaque comparaison élimine environ la moitié des candidats restants. Après une étape, il reste environ $n/2$ éléments. Après deux étapes, il en reste environ $n/4$. Après $k$ étapes, la taille restante est d’environ

$$\frac{n}{2^k}$$

La recherche se termine lorsque cette quantité vaut environ $1$, donc le nombre d’étapes vérifie

$$2^k \approx n$$

En prenant le $\log_2$ des deux côtés, on obtient

$$k \approx \log_2 n$$

C’est pourquoi la recherche binaire passe bien à l’échelle. Une recherche linéaire peut nécessiter jusqu’à $n$ vérifications, mais la recherche binaire n’a besoin que d’assez de vérifications pour continuer à diviser l’intervalle par deux.

Exemple de code de recherche binaire

Voici une version itérative standard en Python :