Vous devez vous connecter pour exécuter votre code.
Hoare 7 — Recherche dichotomique annotée
Écrivez le code C de la recherche dichotomique avec les annotations Hoare complètes (@pre, @post, @invariant, @variant).
Invariant attendu :
cible absente de t[0..lo-1] et t[hi+1..n-1]
Quantité de contrôle attendue :
hi - lo + 1
#include <stdio.h>
// @pre: t est trié en ordre croissant, n >= 0
// @post: retourne l'indice de cible dans t, ou -1 si absente
int dichotomie(int t[], int n, int cible) {
if (n == 0) return -1;
int lo = 0, hi = n - 1;
// @invariant: 0 <= lo <= hi+1 <= n && cible absente de t[0..lo-1] et t[hi+1..n-1]
// @variant: hi - lo + 1
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (t[mid] == cible) return mid;
if (t[mid] < cible) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
int n, cible, t[1000];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &t[i]);
scanf("%d", &cible);
printf("%d\n", dichotomie(t, n, cible));
return 0;
}