CKTIS / C
Binárne vyhľadávanie a lower bound v C
Binárne vyhľadávanie opakovane delí zoradený vyhľadávací rozsah na polovice. Príklad implementuje lower bound: index prvého prvku, ktorý nie je menší ako kľúč, alebo n, ak taký prvok neexistuje. Venuje sa duplicitám, prázdnemu vstupu a bezpečnému výpočtu stredu.
Verzia: C23; repository compiler flag, production runtime not attested
Syntax
size_t lower_bound_int(const int *a, size_t n, int key);Binárne vyhľadávanie vyberie stred rozsahu a zahodí polovicu, ktorá nemôže obsahovať hľadaný výsledok. Predpoklad zoradeného vstupu tu znamená, že a[0..n) je zoradené neklesajúcim spôsobom podľa rovnakého porovnania, aké používa vyhľadávanie. Funkcia túto podmienku nekontroluje; neusporiadaný vstup môže viesť k nesprávnemu výsledku.
Ukážková funkcia lower_bound_int implementuje lower bound: vráti prvý index pos, pre ktorý platí a[pos] >= key, alebo n, ak taký index neexistuje. Pri duplicitách označuje prvý výskyt. Samotný index nepotvrdzuje prítomnosť kľúča: použite test pos < n && a[pos] == key. Vďaka vyhodnocovaniu s krátkym spojením tento test nečíta a[n].
Cyklus udržiava polootvorený rozsah [lo, hi): prvky pred lo sú menšie ako key a prvky od hi po n nie sú menšie ako key. Príkaz hi = mid zachováva možný prvý výsledok, zatiaľ čo lo = mid + 1 preskočí príliš malý prvok. Výraz lo + (hi - lo) / 2 zabraňuje pretečeniu pri sčítaní hraníc. Keď platí lo == hi, obe hranice určujú výsledok.
Pre n > 0 musí a poskytovať aspoň n platných prvkov; počas vyhľadávania sa nesmú meniť. Pre n == 0 táto implementácia prijíma NULL a vracia 0 bez čítania pamäte. Pri poli je časová zložitosť O(log n) pre n >= 2 a pomocná pamäť O(1); predchádzajúce triedenie nie je zahrnuté. C23 je cieľom príznakov kompilátora v repozitári, nie potvrdením produkčného runtime prostredia.
Prí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ýsledok
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ýsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.