Recherche dichotomique et algorithmes gloutons

La recherche dichotomique (ou binaire) permet de trouver un élément dans une liste triée en O(log n) au lieu de O(n) pour la recherche séquentielle. Le principe est de diviser la zone de recherche en deux à chaque étape : on compare l'élément cherché au milieu de la liste, puis on élimine la moitié qui ne peut pas le contenir. Par exemple, dans une liste triée de 1000 éléments, il suffit d'environ 10 comparaisons (car log₂(1000) ≈ 10). Les algorithmes gloutons construisent une solution étape par étape en faisant à chaque fois le choix localement optimal, sans revenir en arrière. Le problème du rendu de monnaie est un exemple classique : on rend toujours la plus grande pièce possible. Cette stratégie ne donne pas toujours la solution optimale globale, mais elle est simple et souvent efficace.