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 | [1] |
Legjobb időbonyolultság |
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
Jegyzetek
Források
Kapcsolódó szócikkek
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.