Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

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.

Sources