Logaritmikus keresés (algoritmus)
A logaritmikus keresés - másnéven bináris keresés (binary search) - egy olyan keresőalgoritmus, amit egy elem rendezett tömbben való keresésére használnak, és azon a felismerésen alapszik, hogy a rendezett tömb adott elemével összehasonlítva a keresett elemet, a keresés a megfelelő intervallumban (ti. az adott elemnél kisebb vagy nagyobb elemek halmazában) folytatható: a keresési intervallum ilyen finomításával így végül megtaláljuk a keresett elemet, ha benne van a rendezett tömbünkben. A keresés során minden egyes iterációban felezni lehet a következő iterációban résztvevő elemek számát, így egy n elemű tömbben O(log n) lépésben megtalálható a keresett elem, vagy megállapítható jelenlétének hiánya a halmazban; az algoritmus innen kapta a nevét.
Tartalomjegyzék |
[szerkesztés] Példa
- A tömb elemei: [1, 2, 3, 4, 5, 6, 7, 8, 9]
- A keresett elem: 3
- A keresési intervallum: [1,9]
Keresési intervallum: a tömb összes eleme között keresünk, és mivel a példában 9 elemű tömbünk van, ezért a keresési intervallum kezdetben[1,9]. Most ha a tömb "középső", ötödik elemét (ami a példában 5) összehasonlítjuk a keresett számmal, a 3-mal, akkor látható, hogy felesleges a keresést a tömbben az 5 után következő számok között folytatnunk, így a keresési intervallumot az eredeti [1,9]-ről [1,4]-re finomíthatjuk.
- A tömb [1,4] intervallumba eső elemei tehát: [1, 2, 3, 4]
Az intervallumban most négy elem található, tehát nincs "középső", így megegyezés szerint egy [u,v] intervallumnak mindig az (u+v)/2 -dik elemét tekintjük "középsőnek", ahol az osztás az egész számokon definiált osztás művelet, ami törtszám esetén az osztás egészrészét adja vissza. A tömb [1,4] intervallumának középső eleme tehát a tömb (1+4)/2 = 2. (második) eleme, ami a példában szereplő tömbben szintén a 2.
Most ismét látható, hogy ha a tömb [1,4] intervallumának "középső" elemét, a 2-t összehasonlítjuk a keresett számmal, a 3-mal, akkor felesleges a keresést az [1,2] intervallumban folytatnunk, így a keresési intervallumot az [1,4]-ről [3,4]-re finomíthatjuk.
- A tömb [3,4] intervallumba eső elemei: [3,4]
A kételemű intervallum "középső" elemét ismét az előző módszer szerint véve kapjuk, hogy (3+4)/2 = 3, tehát a tömb harmadik eleme a tömb [3,4] intervallumának középső eleme. Ezt összehasonlítva a keresett számmal, a 3-mal, látjuk, hogy megtaláltuk a keresett számot, így a keresés sikerrel befejeződik.
[szerkesztés] Pszeudokód
Adott egy A nevű, N darab számot tartalmazó tömb, a tömb indexelése 1-től kezdődik. A keresett szám az X. A pszeudokódban leírt algoritmus arra a problémára ad választ, hogy a tömbben szerepel-e a keresett szám: ha szerepel, az L logikai változót igazra állítjuk.
U := 1;
V := N;
L := Hamis;
Ciklus amíg L Hamis ÉS U<=V
i := (U+V)/2;
HA A[i]=X AKKOR
L := Igaz;
HA A[i]<X AKKOR
U := i+1;
HA A[i]>X AKKOR
V := i-1;
Ciklus vége.
[szerkesztés] Az algoritmus C++ nyelven
A C alapú programozási nyelvekben, így a C++ -ban is a tömbök indexelése nullától kezdődik, így ezt a tényt figyelembe kell venni az implementációnál. A következő, C++ nyelven írt algoritmusban az u és v változók jelzik a mindenkori keresési intervallumot, x pedig a keresett elemet:
U = 0; V = N-1; // ha N a tömbben szereplő elemek száma L = false; // ez a változó jelzi, hogy megtaláltuk-e a keresett elemet while(!L && U<=V) { int i = (U+V)/2; if (A[i] == X) L = true; else if (A[i] < X) U = i+1; else V = i-1; }
[szerkesztés] Rekurzív implementáció
Az algoritmus eddig tárgyalt megvalósításai mind ciklust használtak a probléma megoldásához. Lehetséges azonban rekurzív megoldást is adni a problémára, mégpedig a következő módon:
LOG_KERES(A[1..N], U, V, X)
HA V>U AKKOR
RETURN Hamis;
i := (U+V)/2;
HA A[i]=X AKKOR
RETURN Igaz;
HA A[i]<X AKKOR
RETURN LOG_KERES(A[1..N], i+1, V, X);
HA A[i]>X AKKOR
RETURN LOG_KERES(A[1..N], U, i-1, X);
Függvény vége.
A rekurzív megoldásnál arra kell ügyelni, hogy ha a keresett elem nem szerepel a tömbben, könnyen végtelen hívási sorozathoz juthatunk, ami előbb-utóbb a hívási verem túlcsordulását eredményezi. Ennek érdekében a V>U feltételt be kellett építeni az implementációnkba: ha a keresési intervallum üres halmaz, az elem semmiképpen sem szerepel benne, tehát a visszaadott érték a Hamis.
[szerkesztés] További érdekességek
Az algoritmus természetesen használható csökkenően rendezett tömbökben való keresésre is, ebben az esetben az algoritmusban használt A[i]<X feltételt A[i]>X-re, az A[i]>X feltételt pedig értelemszerűen A[i]<X-re kell cserélni.
Érdekesség még, hogy a fenti algoritmusokban a keresett elemet mindig a keresési intervallum "középső" elemével hasonlítottuk össze, és ennek megfelelően finomítottuk az intervallumot. Lehetséges azonban a keresési intervallum más elemével is elvégezni az összehasonlítást, viszont ebben az esetben a futási idő nem lesz logaritmikus. Például, hogyha a keresési intervallum első elemével hasonlítunk össze, az valójában a rendezett tömbön való lineáris keresés, aminek a futási ideje lineáris, egy n elemű tömbben O(n).
További tulajdonsága még a fenti algoritmusoknak, hogy ha a keresett elem megtalálható a tömbben, akkor nem biztos, hogy U=V (ha azonnal a keresett elemre mutat i). Abban az esetben viszont, ha a keresett elem nem található a tömbben, az U és V által jelzett intervallum azt a helyet fogja jelölni, ahol a keresett elem szerepelne a rendezett tömbben, ha benne lenne.
Például ha a [10,20,30,40,50,60,70,80,90] tömbben keressük az 55-öt, akkor az algoritmus végén U=6, V=5 jelzi azt, hogy az 55-nek a tömb ötödik és hatodik indexű elemei közt kellene elhelyezkednie. A logaritmikus keresés ezen tulajdonságát felhasználhatjuk akár egy rendezett tömbbe való beszúrás művelet megvalósításánál is: ha a tömbnek nem eleme a beszúrandó elem, akkor a logaritmikus keresés által visszaadott U,V helyre beszúrjuk a szóban forgó elemet, majd az ettől jobbra szereplő elemeket eggyel jobbra csúsztatjuk.
