Vous devez vous connecter pour exécuter votre code.
Recherche dichotomique
Implementez la recherche par dichotomie dans un tableau trie.
Invariant attendu :
target absent de x[0..lo-1] et x[hi+1..n-1]
Quantité de contrôle attendue :
hi - lo + 1
#include <stdio.h>
// @pre: x est trie en ordre croissant
// @post: retourne l'indice de target ou -1
int binary_search(int x[], int n, int target) {
if (n == 0) return -1;
int lo = 0, hi = n - 1;
// @invariant: 0 <= lo <= hi+1 <= n
// @variant: hi - lo + 1
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (x[mid] == target) return mid;
if (x[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
int n;
scanf("%d", &n);
int arr[1000];
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
printf("%d\n", binary_search(arr, n));
return 0;
}