Un tableau trié a été décalé circulairement

def minimum_tourne(t):
    """Indice du minimum d'un tableau trie puis DECALE circulairement.

    Precondition  : t est non vide et sans doublon.
    Postcondition : t[r] == min(t).
    """
    assert len(t) > 0
    gauche, droite = 0, len(t) - 1
    while gauche < droite:
        milieu = (gauche + droite) // 2
        if t[milieu] > t[droite]:
            gauche = milieu + 1        # le "creux" est APRES milieu
        else:
            droite = milieu            # il est en milieu, ou avant
    assert t[gauche] == min(t)
    return gauche

**La comparaison se fait avec le bout, pas avec le voisin.** Si $t[\text{milieu}]>t[\text{droite}]$, c'est qu'une rupture existe entre les deux : le minimum est strictement après milieu. Sinon, la partie droite est bien ordonnée et le minimum est en milieu ou avant — d'où droite = milieu sans le $-1$, puisque milieu reste candidat.

Pourquoi « sans doublon » en précondition. Avec des égalités, $t[\text{milieu}]=t[\text{droite}]$ ne permet plus de décider de quel côté chercher : [2, 2, 2, 1, 2] et [2, 1, 2, 2, 2] donnent la même comparaison et ont leur minimum de part et d'autre. Aucune méthode logarithmique n'existe alors ; la précondition n'est pas de la prudence, c'est une nécessité.

Vérification, sur tous les décalages possibles.

assert minimum_tourne([3, 4, 5, 1, 2]) == 3
assert minimum_tourne([1, 2, 3]) == 0       # decalage nul
assert minimum_tourne([2]) == 0

for _ in range(3000):
    n = random.randint(1, 12)
    base = sorted(random.sample(range(100), n))    # sans doublon
    d = random.randrange(n)
    t = base[d:] + base[:d]
    assert t[minimum_tourne(t)] == min(t)

random.sample garantit l'absence de doublon : le test respecte la précondition qu'il annonce. Le décalage $d=0$ est inclus, c'est le cas limite du tableau non décalé.