Informatika gyűjtemény

NézetNyomtat

Bináris keresés

Feladat

Bemenet

Adatok rendezett sorozata tömbben, vagy más címezhető formában ($X[1], X[2], \ldots, X[N]$). Az adatok rekordok, a rekord kulcsa szerint növekvő a rendezés.

Kimenet

Adott x kulcsú adatrekord indexe a SOR változóban, vagy annak jelzése, hogy ilyen kulcs nem szerepel, a VAN változóban.

Algoritmus

Adatok tömbben

:= 1
:= N
:= (+ U) / 2 {Egész osztás}
Ciklus amíg E <= U és T[K].kulcs <> x
    Ha T[K].kulcs < x
    akkor
        E := K + 1
    különben
        U := K - 1
    Elágazás vége
    K := (+ U) / 2 {Egész osztás}
Ciklus vége
VAN := (T[K].kulcs = x)
Ha VAN akkor SOR := K Elágazás vége

Példák

Feladatok