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.