L'algorithme

On souhaite rédiger cet algorithme en Python. On nommera donc def recherche_dichotomique(l, v) la fonction pour rechercher une valeur v dans une liste l précédemment triée. Cette fonction devra renvoyer un booléen indiquant si la valeur est présente ou absente de la liste.

On va ensuite délimiter la position du tableau avec deux variables g et d qui indiqueront les indices de la délimitation :

• Pour tout i inférieur à g, l[i] < v
• Pour tout i supérieur à d, l[i] > v

On va alors répéter le principe de la dichotomie, tant que la valeur de v n'est pas trouvée dans la liste, ou tant qu'il y a toujours des éléments entre g et d. On doit pour cela trouver l'élément central entre g et d, calculable avec la formule \(\frac{g+d}{2}\). On fera attention à obtenir un entier comme résultat.

Une fois cette valeur trouvée, nommons-la m et comparons la valeur associée à son indice à v :

• Si l[m] == v, alors on a trouvé v et on renvoie True.
• Si l[m] < v, alors la borne g est mise à jour, et on recommence.
• Si l[m] > v, alors la borne d est mise à jour, et on recommence.

Si g et d se retrouvent inversés (c'est-à-dire que g > d) alors le programme doit renvoyer False.