Bináris keresés

A bináris keresés vagy logaritmikus keresés rendezett tömb elemei között egy specifikus érték megtalálására alkalmazható rekurzív keresési algoritmus. Logaritmikus keresésnek azért nevezik, mert a szükséges döntések száma az elemek számának kettes alapú logaritmusa vagy ahhoz nagyon közeli.

Bináris keresés
Kategória	keresés
Adatstruktúra	tömb
Legrosszabb időbonyolultság	$O(log_{2}(n))$
Legjobb időbonyolultság	$O(1)$

Az algoritmus

Az algoritmus, miután a két munkaváltozó (A és b) értékét beállította az első, illetve az utolsó elem indexére (x, illetve y), a tömb középső értékétől indul, ellenőrzi, hogy az nagyobb vagy kisebb a keresett számnál. Ha nagyobb, a középső elem indexéből levon egyet, majd annak az a-hoz való átlagolásával kapott szám lesz a következő vizsgált elem indexe, majd a-t beállítja a középső elem indexének szukcesszorára. Ha egyenlő a keresett számmal, az algoritmus visszaadja a középső elem indexét és leáll. Ha pedig kisebb a keresett értéknél, b-hez átlagol, majd b-t beállítja a középső elem előtti elem indexére. Ezután ismételgeti ugyanezt a középső elem helyett az előző lépésben vizsgált elemmel, amíg meg nem találja a vizsgált értéket/nem derül ki egyértelműen, hogy az érték nincs a tömbben.

Pszeudokód

A := x

b := y

f := false // „Benne van-e a keresett érték”-változó

While A <= u && !f:

  k := [(A + b)/2]

  if a[k] < s // s: a keresett érték

    A := k+1

  if a[k] = s:

    f := true

    stop

  if a[k] > s:

    b := k - 1

Források

Négyjegyű függvénytáblázatok, összefüggések és adatok. ISBN 978-963-19-7745-5