Logaritmikus keresés (algoritmus)

A Programozás Wiki wikiből
(Bináris keresés (algoritmus) szócikkből átirányítva)

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.

Példa[szerkesztés]

  • 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.

Pszeudokód[szerkesztés]

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.

Az algoritmus C++ nyelven[szerkesztés]

Legyen A egy rendezett, N hosszú int tömb. Bináris keresés std::lower_bound használatával:

void find(int const *A, size_t N, int v)
{
    int const *i=std::lower_bound(A,A+N,v);
    if(i!=A+N && *i==v)
    std::cout << "megvan, pozíció=" << i-A << std::endl;
    else std::cout << "nincs meg" << std::endl;
}

Vagy ki is írhatjuk az std::lower_bound kódját, ha valamilyen struktúrák tömbjébek akarunk keresni

struct wat
{
    int key;
    // .. meg még minden más
};
void find(wat const *A, size_t N, int v)
{
    size_t b=0,e=N;
    while(b<e)
    {
        size_t m=(b+e)/2;
        if(A[m].key<v)
            b=m+1;
        else e=m;
    }
    if(b!=N && A[i].key==v)
        std::cout << "megvan, pozíció=" << b << std::endl;
    else std::cout << "nincs meg" << std::endl;
}

Rekurzív implementáció[szerkesztés]

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.

További érdekességek[szerkesztés]

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.