def recherche_dichotomique(liste, valeur): # La liste doit être triée pour que la recherche dichotomique fonctionne correctement liste = sorted(liste) # Initialisation des indices de début et de fin pour la recherche debut = 0 fin = len(liste) - 1 # Boucle tant que la partie de la liste à examiner n'est pas réduite à zéro while debut <= fin: # Calcul de l'indice du milieu pour diviser la liste en deux milieu = (debut + fin) // 2 # Vérifie si la valeur au milieu est celle que l'on recherche if liste[milieu] == valeur: # Si c'est le cas, retourne True car la valeur a été trouvée return True # Si la valeur recherchée est plus grande que l'élément au milieu elif liste[milieu] < valeur: # Met à jour le début pour ignorer la première moitié de la liste debut = milieu + 1 # Si la valeur recherchée est plus petite que l'élément au milieu else: # Met à jour la fin pour ignorer la seconde moitié de la liste fin = milieu - 1 # Si la boucle se termine sans trouver la valeur, retourne False return False def test_recherche_dichotomique(): # Cas 1 : Liste vide assert recherche_dichotomique([], 5) == False, "Échec: Liste vide, valeur absente" # Cas 2 : Liste avec un seul élément, valeur présente assert recherche_dichotomique([5], 5) == True, "Échec: Liste avec un seul élément, valeur présente" # Cas 3 : Liste avec un seul élément, valeur absente assert recherche_dichotomique([3], 5) == False, "Échec: Liste avec un seul élément, valeur absente" # Cas 4 : Liste triée, valeur présente au début assert recherche_dichotomique([1, 3, 5, 7, 9], 1) == True, "Échec: Liste triée, valeur présente au début" # Cas 5 : Liste triée, valeur présente au milieu assert recherche_dichotomique([1, 3, 5, 7, 9], 5) == True, "Échec: Liste triée, valeur présente au milieu" # Cas 6 : Liste triée, valeur présente à la fin assert recherche_dichotomique([1, 3, 5, 7, 9], 9) == True, "Échec: Liste triée, valeur présente à la fin" # Cas 7 : Liste triée, valeur absente assert recherche_dichotomique([1, 3, 5, 7, 9], 4) == False, "Échec: Liste triée, valeur absente" # Cas 8 : Liste non triée, valeur présente (la fonction trie automatiquement) assert recherche_dichotomique([7, 1, 9, 3, 5], 3) == True, "Échec: Liste non triée, valeur présente" # Cas 9 : Liste non triée, valeur absente assert recherche_dichotomique([7, 1, 9, 3, 5], 8) == False, "Échec: Liste non triée, valeur absente" # Cas 10 : Liste avec des éléments répétitifs, valeur présente assert recherche_dichotomique([1, 3, 3, 3, 5, 7, 9], 3) == True, "Échec: Liste avec répétitions, valeur présente" # Cas 11 : Liste avec des éléments répétitifs, valeur absente assert recherche_dichotomique([1, 3, 3, 3, 5, 7, 9], 4) == False, "Échec: Liste avec répétitions, valeur absente" print("Tous les tests sont passés avec succès !") # Exécuter le jeu de tests test_recherche_dichotomique()