CKTIS / C
Wyszukiwanie binarne i lower bound w C
Wyszukiwanie binarne (binary search) zawęża posortowany zakres o połowę. Przykład implementuje lower bound: indeks pierwszego elementu nie mniejszego od klucza albo n, jeśli taki element nie istnieje. Omawia duplikaty, pusty zakres i bezpieczne obliczanie środka.
Wersja: C23; repository compiler flag, production runtime not attested
Składnia
size_t lower_bound_int(const int *a, size_t n, int key);Wyszukiwanie binarne (binary search) wybiera środek zakresu i odrzuca połowę, która nie może zawierać szukanego wyniku. Warunek uporządkowania danych (sorted input precondition) oznacza tutaj, że a[0..n) jest posortowane niemalejąco według tego samego porównania, którego używa wyszukiwanie. Funkcja nie sprawdza tego warunku; dla nieuporządkowanych danych wynik może być błędny.
Przykładowa funkcja lower_bound_int realizuje lower bound: zwraca pierwszy indeks pos, dla którego a[pos] >= key, albo n, jeśli go nie ma. Przy duplikatach wskazuje pierwsze wystąpienie. Sam indeks nie potwierdza obecności klucza: potrzebny jest test pos < n && a[pos] == key. Dzięki krótkiemu spięciu nie odczytuje on a[n].
Pętla utrzymuje półotwarty zakres [lo, hi): elementy przed lo są mniejsze od key, a elementy od hi do n są nie mniejsze od key. Instrukcja hi = mid zachowuje możliwy pierwszy wynik, natomiast lo = mid + 1 pomija zbyt mały element. Wzór lo + (hi - lo) / 2 unika przepełnienia sumy granic. Gdy lo == hi, obie granice wyznaczają wynik.
Dla n > 0 wskaźnik a musi udostępniać co najmniej n poprawnych elementów; nie wolno zmieniać ich podczas wyszukiwania. Dla n == 0 ta implementacja akceptuje NULL i zwraca 0 bez odczytu. Na tablicy czas wynosi O(log n) dla n >= 2, a pamięć pomocnicza O(1); koszt wcześniejszego sortowania nie jest wliczony. C23 jest celem flagi kompilatora repozytorium, nie potwierdzeniem środowiska produkcyjnego.
Przykłady
#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;
}
Wynik
key=3 pos=1 found=1 key=4 pos=3 found=0 key=9 pos=4 found=0 empty pos=0
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.