INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q051 — Écrire l’invariant de boucle permettant de prouver la correction de la recherche binaire.
Madame, Monsieur, Je vous remercie de cette question portant sur la preuve de correction de la recherche binaire. Voici l'invariant de boucle permettant d'établir cette correction, avec sa justification complète. L'invariant de boucle classique pour la recherche binaire s'énonce ainsi, en supposant que l'on cherche une valeur x dans un tableau T trié par ordre croissant, indicé de 0 à n-1, avec deux bornes g (gauche) et d (droite) telles que la zone de recherche soit l'intervalle [g, d] : Invariant : à chaque itération, si x est présent dans le tableau, alors il se trouve dans l'intervalle [g, d]. Autrement dit, x n'est ni strictement avant g, ni strictement après d. Formellement, pour tout indice i : - si i < g, alors T[i] < x ; - si i > d, alors T[i] > x. Justification de la correction : Initialisation. Avant la première itération, on pose g = 0 et d = n-1. L'intervalle couvre tout le tableau, donc l'invariant est trivialement vrai : si x est présent, il est bien dans [0, n-1]. Conservation. On calcule m = (g + d) / 2 (division entière). Trois cas : - si T[m] = x, on a trouvé la valeur, l'algorithme se termine correctement ; - si T[m] < x, alors, comme le tableau est trié, tous les éléments d'indice inférieur ou égal à m sont strictement inférieurs à x. On pose g = m + 1, et l'invariant reste vrai : x ne peut être qu'à droite de m ; - si T[m] > x, tous les éléments d'indice supérieur ou égal à m sont strictement supérieurs à x. On pose d = m - 1, et l'invariant reste vrai : x ne peut être qu'à gauche de m. Dans tous les cas, l'invariant est préservé d'une itération à la suivante. Terminaison. À chaque itération, la taille de l'intervalle d - g + 1 diminue strictement (puisque l'on exclut toujours m), donc la boucle se termine. Conclusion. À la sortie de la boucle, on a g > d, c'est-à-dire un intervalle vide. L'invariant affirme alors que si x était présent, il serait dans un intervalle vide, ce qui est impossible. On en déduit que x est absent du tableau, et l'algorithme renvoie correctement l'échec. Si au contraire on a rencontré T[m] = x en cours de route, la valeur a été correctement localisée. Cet invariant est la clé de la preuve : il exprime précisément que la zone de recherche contient toujours la cible si elle existe, et la décroissance de l'intervalle garantit la terminaison. Confiance : 97 %. Il s'agit d'un résultat standard et bien établi de l'algorithmique ; la seule marge d'incertitude tient aux variantes de formulation (bornes incluses ou exclues, choix de la division entière), qui ne changent pas le principe mais peuvent modifier les détails de l'énoncé. Je vous prie d'agréer, Madame, Monsieur, l'expression de mes salutations distinguées.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.