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.