Les deux plus proches, sans boucles imbriquées

def plus_proches(L):
    T = sorted(L)                  # sorted RENVOIE une copie triee
    meilleure = T[1] - T[0]
    couple = (T[0], T[1])
    for i in range(len(T) - 1):
        d = T[i+1] - T[i]
        if d < meilleure:
            meilleure = d
            couple = (T[i], T[i+1])
    return couple

La propriété. Dans une liste triée, deux valeurs réalisant l'écart minimal sont voisines. Démontrons-le : soient $i<j$ deux indices avec $j>i+1$. La liste étant croissante, tous les écarts intermédiaires sont positifs, donc

$$T[i+1]-T[i]\le T[j]-T[i].$$

La paire voisine $(T[i],T[i+1])$ fait donc au moins aussi bien que la paire $(T[i],T[j])$. Il est inutile d'examiner autre chose que les $n-1$ paires voisines.

Le coût. La boucle fait $n-1$ soustractions ; c'est le tri qui domine, avec de l'ordre de $n\log n$ opérations, contre $\frac{n(n-1)}{2}$ pour les boucles imbriquées. Sur $n=10^4$ : environ $1,3\times 10^5$ opérations au lieu de $5\times 10^7$, soit quelques millisecondes au lieu de plusieurs secondes.

Le point à retenir. On a payé un tri pour supprimer une boucle, et le marché est bon. Mais on perd l'ordre initial : pour rendre les indices d'origine et non les valeurs, il faudrait trier des couples (valeur, indice).