CKTIS / C
Recherche binaire et lower bound en C
La recherche binaire réduit de moitié, à chaque étape, une plage de recherche triée. L’exemple implémente la lower bound : l’indice du premier élément qui n’est pas inférieur à la clé, ou n s’il n’y en a pas. Il aborde les doublons, l’entrée vide et le calcul sûr du milieu.
Version : C23; repository compiler flag, production runtime not attested
Syntaxe
size_t lower_bound_int(const int *a, size_t n, int key);La recherche binaire choisit le milieu d’une plage et élimine la moitié qui ne peut pas contenir le résultat recherché. La précondition d’entrée triée signifie ici que a[0..n) est trié dans l’ordre non décroissant selon la même comparaison que celle utilisée par la recherche. La fonction ne vérifie pas cette condition ; une entrée non triée peut produire un résultat incorrect.
La fonction d’exemple lower_bound_int implémente la lower bound : elle renvoie le premier indice pos tel que a[pos] >= key, ou n si aucun élément ne vérifie cette condition. En présence de doublons, elle désigne la première occurrence. L’indice seul ne confirme pas la présence de la clé : utilisez le test pos < n && a[pos] == key. L’évaluation en court-circuit empêche ce test de lire a[n].
La boucle maintient la plage semi-ouverte [lo, hi) : les éléments avant lo sont inférieurs à key, et ceux de hi à n ne sont pas inférieurs à key. L’instruction hi = mid conserve un éventuel premier résultat, tandis que lo = mid + 1 écarte un élément trop petit. L’expression lo + (hi - lo) / 2 évite le débordement dû à l’addition des bornes. Lorsque lo == hi, les deux bornes déterminent le résultat.
Pour n > 0, a doit fournir au moins n éléments valides ; ils ne doivent pas changer pendant la recherche. Pour n == 0, cette implémentation accepte NULL et renvoie 0 sans lire la mémoire. Sur un tableau, le temps d’exécution est O(log n) pour n >= 2 et l’espace auxiliaire est O(1) ; le tri préalable n’est pas inclus. C23 est la cible des options de compilation du dépôt, et non une attestation de l’environnement d’exécution en production.
Exemples
#include <stddef.h>
#include <stdio.h>
static size_t lower_bound_int(const int *a, size_t n, int key)
{
size_t lo = 0;
size_t hi = n;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] < key) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
int main(void)
{
const int a[] = {1, 3, 3, 7};
const size_t n = sizeof a / sizeof a[0];
const int keys[] = {3, 4, 9};
for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
size_t pos = lower_bound_int(a, n, keys[i]);
int found = pos < n && a[pos] == keys[i];
printf("key=%d pos=%zu found=%d\n", keys[i], pos, found);
}
printf("empty pos=%zu\n", lower_bound_int(NULL, 0, 3));
return 0;
}
Résultat
key=3 pos=1 found=1 key=4 pos=3 found=0 key=9 pos=4 found=0 empty pos=0
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.