Chercher en coupant en deux

Ton ami pense à un nombre entre 1 et 100. Tu as le droit de poser des questions. Il répond seulement : « Plus grand » ou « Plus petit ».

Tu ne vas pas dire 1, puis 2, puis 3. Tu dirais 50. Et si c'est « plus petit », tu sais déjà que la moitié des nombres ne sert plus.

Cette ruse est un algorithme célèbre. Tu vas l'écrire.

Le milieu de 1 et 100 est (1 + 100) divisé par 2. Cela donne 50,5. Mais une case ou un nombre entier ne s'écrit pas avec une virgule.

En Python, la division entière // garde la partie entière : 101 // 2 donne 50. On l'utilise toujours pour le milieu.

secret = 37
bas = 1
haut = 100
proposition = (bas + haut) // 2
coups = 1
print("Coup", coups, ": je propose", proposition)

while proposition != secret:
    if proposition < secret:
        bas = proposition + 1
    else:
        haut = proposition - 1
    proposition = (bas + haut) // 2
    coups = coups + 1
    print("Coup", coups, ": je propose", proposition)

print("Trouvé en", coups, "coups !")

# Change secret en 1, puis en 100. Combien de coups faut-il ?

Pour chercher dans une liste, on fait pareil. Mais la liste doit être triée, du plus petit au plus grand. Sinon, « plus petit » ne veut rien dire.

On garde deux numéros de case : debut et fin. La valeur est forcément entre les deux. On regarde la case du milieu.

Exemple : on cherche 40 dans 3, 8, 12, 15, 21, 27, 34, 40, 46, 52, 60. Il y a 11 cases, de 0 à 10.