Catégories
Non classé

Correction de l’algorithme de recherche dichotomique dans une liste triée

Pour les groupes de mardi et de jeudi 15h-16h, la preuve que j’ai écrite au tableau contient une erreur. Voici la version corrigée :

Si \(e\in L\), alors aucun return ne sera exécuté avant le return False final : l’algorithme renvoie bien False comme prévu.

Si \(e\in L\) alors on a l’invariant de boucle suivant : à toute étape \(n\) de la boucle while, on a $$ e\in L[a_n:b_n]$$ (se montre rapidement par récurrence). En conséquence, en sortie de boucle while on a \(e=L[a_M]\) ou \(e=L[a_M+1]\) et ces deux cas sont testés, renvoyant bien un indice qui convient.

J’ai aussi mis l’algorithme d’exponentiation rapide en ligne pour ceux que ça intéresse et les corrections des questions sur la complexité, la terminaison et la correction. Il y a un variant et un invariant de boucle intéressants à aller voir.

Bien sûr, essayez ces questions (surtout l’algorithme) avant de lire le corrigé si vous voulez en tirer quelque chose.

Laisser un commentaire