Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C

Binární vyhledávání a lower bound v C

Binární vyhledávání opakovaně půlí seřazený vyhledávací rozsah. Příklad implementuje lower bound: index prvního prvku, který není menší než klíč, nebo n, pokud takový prvek neexistuje. Zabývá se duplicitami, prázdným vstupem a bezpečným výpočtem středu.

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

Syntaxe

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

Binární vyhledávání zvolí střed rozsahu a zahodí polovinu, která nemůže obsahovat hledaný výsledek. Předpoklad seřazeného vstupu zde znamená, že a[0..n) je seřazeno neklesajícím způsobem podle stejného porovnání, jaké používá vyhledávání. Funkce tuto podmínku nekontroluje; neuspořádaný vstup může vést k nesprávnému výsledku.

Ukázková funkce lower_bound_int implementuje lower bound: vrací první index pos, pro který platí a[pos] >= key, nebo n, pokud žádný takový index není. U duplicit označuje první výskyt. Samotný index nepotvrzuje, že klíč existuje: použijte test pos < n && a[pos] == key. Díky vyhodnocování s krátkým spojením tento test nečte a[n].

Cyklus udržuje polootevřený rozsah [lo, hi): prvky před lo jsou menší než key a prvky od hi do n nejsou menší než key. Příkaz hi = mid zachovává možný první výsledek, zatímco lo = mid + 1 přeskočí příliš malý prvek. Výraz lo + (hi - lo) / 2 zabraňuje přetečení při sčítání mezí. Když platí lo == hi, obě meze určují výsledek.

Pro n > 0 musí a poskytovat alespoň n platných prvků; během vyhledávání se nesmějí měnit. Pro n == 0 tato implementace přijímá NULL a vrací 0, aniž by četla paměť. U pole je časová složitost O(log n) pro n >= 2 a pomocná paměť O(1); předchozí řazení není zahrnuto. C23 je cílem příznaků kompilátoru v repozitáři, nikoli potvrzením produkčního běhového prostředí.

Příklady

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

Výsledek

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

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje