Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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.

Źródła