Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C

Binarno iskanje in lower bound v C

Binarno iskanje večkrat razpolovi urejeno iskalno območje. Primer implementira lower bound: indeks prvega elementa, ki ni manjši od ključa, ali n, če takega elementa ni. Obravnava dvojnike, prazen vhod in varen izračun sredine.

Različica: C23; repository compiler flag, production runtime not attested

Sintaksa

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

Binarno iskanje izbere sredino območja in zavrže polovico, ki ne more vsebovati iskanega rezultata. Predpostavka urejenega vhoda tukaj pomeni, da je a[0..n) urejeno naraščajoče ali enako po istem načinu primerjave, kot ga uporablja iskanje. Funkcija tega pogoja ne preveri; neurejen vhod lahko povzroči napačen rezultat.

Zgledna funkcija lower_bound_int implementira lower bound: vrne prvi indeks pos, za katerega velja a[pos] >= key, ali n, če takega indeksa ni. Pri dvojnikih označuje prvo pojavitev. Sam indeks ne potrjuje, da je ključ prisoten: uporabite preizkus pos < n && a[pos] == key. Zaradi kratkostičnega vrednotenja ta preizkus ne bere a[n].

Zanka vzdržuje polodprto območje [lo, hi): elementi pred lo so manjši od key, elementi od hi do n pa niso manjši od key. Ukaz hi = mid ohrani morebitni prvi rezultat, medtem ko lo = mid + 1 preskoči premajhen element. Izraz lo + (hi - lo) / 2 prepreči prekoračitev pri seštevanju mej. Ko velja lo == hi, obe meji določata rezultat.

Za n > 0 mora a zagotavljati vsaj n veljavnih elementov; med iskanjem se ne smejo spreminjati. Za n == 0 ta implementacija sprejme NULL in vrne 0, ne da bi brala pomnilnik. Pri tabeli je časovna zahtevnost O(log n) za n >= 2, dodatni pomnilnik pa O(1); predhodno urejanje ni vključeno. C23 je cilj zastavic prevajalnika v repozitoriju, ne potrditev produkcijskega izvajalnega okolja.

Primeri

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

Rezultat

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

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri