C Programozas

Bináris Keresés

Sok fajta keresési algoritmus létezik. Ma megnézzük az egyik leggyorsabbat, a bináris keresést és az ahhoz tartozó C nyelvű implementációt.

 

Mi a bináris keresés?

A bináris keresés egy rendezett listán belül képes keresni. Az elméleti koncepciója az, hogy ha létezik a rendezett lista, akkor a keresett számról egyértelműen el tudom dönteni, hogy az aktuális számtól kisebb-e vagy nagyobb és ez alapján egyértelműen tudom, hogy a lista melyik maradék részében kell tovább keresnem. Az algoritmus a keresési listát mindig megfelezi, attól függően, hogy a keresett szám kisebb-e vagy nagyobb az aktuális lista elemnél, neve az algoritmus működési elvére utal. A bináris keresés rendkívül optimális, a futási komplexitása O(log N), tehát logaritmikus, ami azt jelenti, hogy nagyon lassan nő csak a futási ideje, vagyis milliós nagyságrendű adatoknál is csak pár lépésre van szüksége általában. Nézzünk egy példát:

 

  • A lista: [1,2,3,4,5]
  • Keresett szám: {4}

Az algoritmus futásának lépései:

  1. Keresési lista: [1,2,3,4,5]
  2. A lista középső eleme: [3]
  3. Aktuális szám: [3] < {4} -> Jobbra kell keresnem a maradék listában
  4. Felezés! Új keresési lista: [4,5]
  5. Aktuális szám: [4] = {4} -> Keresett szám megtalálva, a keresésnek vége

 

A bináris keresés kihasználja a lista rendezett tulajdonságát, rendezetlen listán nem is használható. Az algoritmus bemenete a lista első és utolsó elemének az indexe, illetve a keresett érték. A trükk az, hogy a bináris keresés mindig a keresési listát felezi, azáltal, hogy az első és utolsó elemének az indexét folyamatosan frissíti. Majd a frissített indexeknek veszi a közepét és azt az elemet hasonlítja össze a keresettel majd ismétli a folyamatot.
Nézzük meg a fenti példát még egyszer, most már feltüntetve az indexeket is (a tömbök indexe mindig 0-ról indul!):

 

  • A lista: [1,2,3,4,5]
  • Keresett szám: {4}
  • Első elem indexe (EI)
  • Utolsó elem indexe (UI)
  • Aktuális index (AI)

Az algoritmus futásának lépései:

  1. Keresési lista: [1,2,3,4,5]
    1. EI = 0
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 0 + ((4-0)/2) = 2
  2. Aktuális szám: [3] < {4} -> Jobbra kell keresnem a maradék listában
  3. Felezés! Új keresési lista: [4,5]
    1. EI = AI+1 = 3
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 3 + ((4-3)/2) = 3
  4. Aktuális szám: [4] = {4} -> Keresett szám megtalálva, a keresésnek vége

 

Hogyan frissítődnek az indexek?

Az első körben az első elem indexe és az utolsó elem indexe statikus értékeket kapnak. A középső elem indexe mindig az alábbi képlet alapján számolódik: Első elem indexe + ((Utolsó elem indexe – Első elem indexe)/2)
Aztán a további körökben a talált értéktől függően vagy az első elem vagy az utolsó elem indexét frissítjük, a középső elem indexe mellett:

  • Első elem indexe = Középső elem indexe + 1;
  • Utolsó elem index = Középső elem indexe – 1;
  • Középső elem indexe = Első elem indexe + ((Utolsó elem indexe – Első elem indexe)/2)

 

Meddig fut az algoritmus?

Két opció létezik, vagy megtalálja az algoritmus a keresett számot és akkor leáll vagy nem találja meg a keresett számot. Persze ekkor is leáll, de ilyenkor az lesz a kilépési feltétel, hogy az első elem indexe nagyobb mint az utolsó elem indexe, azaz nincs több ellenőrizendő elem a listában. Nézzük meg, hogy mi történik ha a 6-os a keresett szám a fenti listában:

 

  • A lista: [1,2,3,4,5]
  • Keresett szám: {6}
  • Első elem indexe (EI)
  • Utolsó elem indexe (UI)
  • Aktuális index (AI)

Az algoritmus futásának lépései:

  1. Keresési lista: [1,2,3,4,5]
    1. EI = 0
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 0 + ((4-0)/2) = 2
  2. Aktuális szám: [3] < {6} -> Jobbra kell keresnem a maradék listában
  3. Felezés! Új keresési lista: [4,5]
    1. EI = AI+1 = 3
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 3 + ((4-3)/2) = 3
  4. Aktuális szám: [4] < {6} -> Jobbra kell keresnem a maradék listában
  5. Felezés! Új keresési lista: [5]
    1. EI = AI+1 = 4
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 4 + ((4-4)/2) = 4
  6. Aktuális szám: [5] < {6} -> Jobbra kell keresnem a maradék listában
  7. Felezés!
    1. EI = AI+1 = 5
    2. UI = 4
  8. EI > UI -> Kilépés

 

Nézzük meg az algoritmushoz tartozó C nyelvű implementációt, amit innen a blogról is le tudtok tölteni. Maga az algoritmus a következő:

 

uint8_t lowIndex_u8 = 0;
uint8_t highIndex_u8 = (numberOfElements_u8-1);
bool targetFound_b = false;

/**
* Until the target number is not found
* OR
* Out of unchecked elements
*/
while ((targetFound_b == false) && (lowIndex_u8 <= highIndex_u8))
{

(*searchedIndex_pu8) = lowIndex_u8 + ((highIndex_u8-lowIndex_u8)/2);

if (orderedList_pu8[(*searchedIndex_pu8)] == targetNumber_u8)
{

/** Current number is equal to the searched one */
targetFound_b = true;

}
else if (orderedList_pu8[(*searchedIndex_pu8)] < targetNumber_u8)
{

/** Current number is lower than the searched one */
lowIndex_u8 = ((*searchedIndex_pu8)+1);

}
else
{

/** Current number is higher than the searched one */
highIndex_u8 = ((*searchedIndex_pu8)-1);

}

}

return targetFound_b;

 

Nézzük meg sorról sorra, hogy mi is történik pontosan:

A ciklus addig fut, ameddig meg nem találja a keresett számot vagy amíg az Első elem indexe nem nagyobb az Utolsó elem indexénél:

while ((targetFound_b == false) && (lowIndex_u8 <= highIndex_u8))
{

}

 

Középső index frissítése:

(*searchedIndex_pu8) = lowIndex_u8 + ((highIndex_u8-lowIndex_u8)/2);

 

Aktuális elem összehasonlítása a keresettel:

Megegyezik:

if (orderedList_pu8[(*searchedIndex_pu8)] == targetNumber_u8)
{

/** Current number is equal to the searched one */
targetFound_b = true;

}

 

Kisebb:

else if (orderedList_pu8[(*searchedIndex_pu8)] < targetNumber_u8)
{

/** Current number is lower than the searched one */
lowIndex_u8 = ((*searchedIndex_pu8)+1);

}

 

Nagyobb:

else
{

/** Current number is higher than the searched one */
highIndex_u8 = ((*searchedIndex_pu8)-1);

}

 

A teljes programot innen tudjátok letölteni.

Ez volt tehát a bináris keresés és a hozzá tartozó C nyelvű implementáció. A legtöbb programozási nyelv rendelkezik saját implementációval az ehhez hasonló alapvető algoritmusokról, így például a Java is, C nyelvben viszont nem ismerek ilyen beépített könyvtárat sajnos. Remélem sikerült egy átfogó képet adni erről a nagyon hasznos keresési algoritmusról.

Bajor Tamás - Programozz Te Is!

Hello, Bajor Tamás vagyok, a Programozz Te Is oldal alapítója és oktatója. Kösz, hogy itt vagy és éppen az én cikkem olvasására fordítod a drága idődet! Azért dolgozom minden nap, hogy neked segítsek a programozás világában minél profibban elmélyülni. A cikkek egyetlen írójaként rengeteg munkát és energiát fektetek mind az oldalba, mind pedig az oktatásba!

 

Arra kérlek, ha tetszett cikk amit olvastál vagy szívesen veszed az ingyenes anyagokat akkor dobj egy Like-ot a Facebook-on, ezzel is támogatva a munkámat. Ez egy apró kattintás neked, de hatalmas segítség nekem!