WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C

Binäre Suche und Lower Bound in C

Die binäre Suche halbiert wiederholt einen sortierten Suchbereich. Das Beispiel implementiert Lower Bound: den Index des ersten Elements, das nicht kleiner als der Schlüssel ist, oder n, falls es keines gibt. Behandelt werden Duplikate, leere Eingaben und eine sichere Berechnung der Mitte.

Version: C23; repository compiler flag, production runtime not attested

Syntax

size_t lower_bound_int(const int *a, size_t n, int key);

Die binäre Suche wählt die Mitte eines Bereichs und verwirft die Hälfte, die das gesuchte Ergebnis nicht enthalten kann. Die Voraussetzung sortierter Eingabedaten bedeutet hier, dass a[0..n) nach derselben Vergleichsregel wie bei der Suche nicht absteigend sortiert ist. Die Funktion prüft diese Voraussetzung nicht; bei unsortierten Daten kann das Ergebnis falsch sein.

Die Beispielfunktion lower_bound_int implementiert Lower Bound: Sie gibt den ersten Index pos zurück, für den a[pos] >= key gilt, oder n, falls es keinen gibt. Bei Duplikaten bezeichnet sie das erste Vorkommen. Der Index allein bestätigt nicht, dass der Schlüssel vorhanden ist: Verwenden Sie den Test pos < n && a[pos] == key. Durch Kurzschlussauswertung liest dieser Test a[n] nicht.

Die Schleife hält den halboffenen Bereich [lo, hi) aufrecht: Elemente vor lo sind kleiner als key, und Elemente von hi bis n sind nicht kleiner als key. Die Anweisung hi = mid behält ein mögliches erstes Ergebnis bei, während lo = mid + 1 ein zu kleines Element überspringt. Der Ausdruck lo + (hi - lo) / 2 vermeidet einen Überlauf beim Addieren der Grenzen. Wenn lo == hi gilt, bestimmen beide Grenzen das Ergebnis.

Für n > 0 muss a mindestens n gültige Elemente bereitstellen; diese dürfen sich während der Suche nicht ändern. Für n == 0 akzeptiert diese Implementierung NULL und gibt 0 zurück, ohne Speicher zu lesen. Bei einem Array beträgt die Laufzeit für n >= 2 O(log n), der zusätzliche Speicherbedarf O(1); eine vorherige Sortierung ist nicht eingerechnet. C23 ist das Ziel der Compiler-Flags des Repositorys, keine Bestätigung der Produktionslaufzeitumgebung.

Beispiele

#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;
}

Ergebnis

key=3 pos=1 found=1
key=4 pos=3 found=0
key=9 pos=4 found=0
empty pos=0

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen