Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

Binarno pretraživanje i lower bound u C-u

Binarno pretraživanje opetovano prepolavlja sortirani raspon pretraživanja. Primjer implementira lower bound: indeks prvog elementa koji nije manji od ključa ili n ako takav element ne postoji. Obrađuje duplikate, prazan unos i siguran izračun sredine.

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

Sintaksa

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

Binarno pretraživanje odabire sredinu raspona i odbacuje polovicu koja ne može sadržavati traženi rezultat. Preduvjet sortiranog ulaza ovdje znači da je a[0..n) sortiran neopadajućim redoslijedom prema istom načinu usporedbe koji upotrebljava pretraživanje. Funkcija ne provjerava taj uvjet; nesortirani ulaz može dati netočan rezultat.

Primjer funkcije lower_bound_int implementira lower bound: vraća prvi indeks pos za koji vrijedi a[pos] >= key ili n ako takav indeks ne postoji. Kod duplikata označava prvo pojavljivanje. Sam indeks ne potvrđuje prisutnost ključa: upotrijebite provjeru pos < n && a[pos] == key. Kratko spajanje sprječava da ta provjera čita a[n].

Petlja održava poluotvoreni raspon [lo, hi): elementi prije lo manji su od key, a elementi od hi do n nisu manji od key. Naredba hi = mid zadržava mogući prvi rezultat, dok lo = mid + 1 preskače premalen element. Izraz lo + (hi - lo) / 2 izbjegava prekoračenje pri zbrajanju granica. Kada vrijedi lo == hi, obje granice određuju rezultat.

Za n > 0, a mora sadržavati najmanje n valjanih elemenata koji se ne smiju mijenjati tijekom pretraživanja. Za n == 0, ova implementacija prihvaća NULL i vraća 0 bez čitanja memorije. Za polje je vremenska složenost O(log n) za n >= 2, a dodatni prostor O(1); prethodno sortiranje nije uključeno. C23 je cilj zastavica prevoditelja u repozitoriju, a ne potvrda produkcijskog izvršnog okruženja.

Primjeri

#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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori