📝 Fiche de révision — Dichotomie, k plus proches voisins, gloutons

✂️ Recherche dichotomique (tableau trié)

debut, fin = 0, len(t) - 1
while debut <= fin:
    m = (debut + fin) // 2
    if t[m] == v: return m
    elif t[m] < v: debut = m + 1
    else: fin = m - 1
return -1

• Précondition : t trié (sinon résultat faux).
• Terminaison : variant fin - debut + 1, entier, strictement décroissant, minoré par 0.
• Invariant : si v est dans t, il est dans t[debut..fin].
• Coût : $\log_2 n$ tours : $n = 1\,000 \to 10$ ; $10^6 \to 20$ ; $10^9 \to 30$ ; doubler n ajoute une comparaison.
• Déroulement : tableau debut / fin / m / t[m].

🎯 k plus proches voisins

1. Distance du nouvel élément à chaque exemple ($\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$).
2. Trier par distance, garder les $k$ premiers.
3. Compter les classes, renvoyer la majoritaire.

• $k$ impair ; petit $k$ sensible au bruit, grand $k$ trop lisse ; tester plusieurs $k$.
• Grandeurs comparables (normaliser).
• Apprentissage : la connaissance est dans les exemples ; coût : une distance par exemple + tri.

🍰 Algorithmes gloutons

• Choix localement meilleur à chaque étape, sans retour ; rapide (tri + parcours) ; optimal seulement parfois.
• Rendu de monnaie : plus grande pièce ≤ reste ; optimal pour $200, 100, 50, 20, 10, 5, 2, 1$ ; pas pour $\{4, 3, 1\}$ : $6 = 4+1+1$ (3) contre $3+3$ (2).
• Sac à dos : trier par valeur/poids décroissant, prendre tant que ça tient ; peut rater l'optimum (capacité 10 : (6 kg, 60) pris seul = 60, contre (5, 45) + (5, 45) = 90).
• Méthode algorithmique parmi d'autres (exhaustive, dynamique en terminale).

⚠️ Pièges à éviter

📌 À retenir

1. Dichotomie : milieu, moitié, variant, log₂ n.
2. kNN : distances, k plus proches, vote.
3. Glouton : choix local, rapide, parfois non optimal.