Bináris keresési algoritmus EXAMPLE-vel

Mielőtt megtanulnánk a bináris keresést, tanuljuk meg:

Mi az a Keresés?

A keresés egy olyan segédprogram, amely lehetővé teszi a felhasználók számára, hogy dokumentumokat, fájlokat, adathordozókat vagy bármilyen más típusú adatot találjanak az adatbázisban. A keresés azon az egyszerű elven működik, hogy a kritériumokat össze kell egyeztetni a rekordokkal, és megjeleníteni a felhasználó számára. Ily módon a legalapvetőbb keresési funkció működik.

Mi az a bináris keresés?

A bináris keresés egy speciális típusú keresési algoritmus, amely az elemek rendezett listájából talál meg és kér le adatokat. Alapvető működési elve a lista adatainak felezése, amíg meg nem találja a kívánt értéket, és megjelenik a felhasználó számára a keresési eredményben. A bináris keresés közismert nevén a félintervallumú keresés vagy logaritmikus keresés.

Hogyan működik a bináris keresés?

A bináris keresés a következő módon működik:

• A keresési folyamat a rendezett adattömb középső elemének megkeresésével indul
• Ezt követően a kulcsértéket összehasonlítja az elemmel
• Ha a kulcsérték kisebb, mint a középső elem, akkor a keresés a felső értékeket a középső elemhez elemzi összehasonlítás és egyeztetés céljából.
• Abban az esetben, ha a kulcsérték nagyobb, mint a középső elem, akkor a keresés az alacsonyabb értékeket a középső elemre elemzi összehasonlítás és egyeztetés céljából.

Példa bináris keresésre

Nézzünk egy szótár példáját. Ha meg kell találnia egy bizonyos szót, senki nem megy végig az egyes szavakon egymás után, hanem véletlenszerűen megkeresi a legközelebbi szavakat, hogy megkeresse a kívánt szót.

A fenti kép a következőket szemlélteti:

1. Van egy 10 számjegyű tömbje, és meg kell találni az 59-es elemet.
2. Az összes elemet 0 és 9 közötti indexszel jelöljük. Most a tömb közepét számítjuk ki. Ehhez vegye az index bal és jobb szélső értékét, és elosztja 2-vel. Az eredmény 4.5, de mi a legalacsonyabb értéket vesszük. Ezért a középső 4.
3. Az algoritmus az összes elemet a középsőtől (4) a legalacsonyabb korlátig dobja, mivel az 59 nagyobb, mint 24, és most már csak 5 elem marad a tömbben.
4. Most az 59 nagyobb, mint 45, és kisebb, mint 63. A középső 7. Így a jobb oldali indexérték középsővé válik – 1, ami 6-nak felel meg, a bal oldali indexérték pedig ugyanaz marad, mint korábban, ami 5.
5. Ezen a ponton tudja, hogy az 59 a 45 után következik. Így a bal oldali index, amely 5, szintén középsővé válik.
6. Ezek az iterációk mindaddig folytatódnak, amíg a tömb egyetlen elemre csökken, vagy a keresendő elem a tömb közepe lesz.

Példa 2

Nézzük meg a következő példát, hogy megértsük a bináris keresés működését

1. Rendezett értékek tömbje 2 és 20 között van, és meg kell találnia a 18-at.
2. Az alsó és felső határ átlaga (l + r) / 2 = 4. A keresett érték nagyobb, mint a 4.
3. A középértéknél kisebb tömbértékeket a rendszer kihagyja a keresésből, és a 4-es középértéknél nagyobb értékeket keresi.
4. Ez egy ismétlődő felosztási folyamat mindaddig, amíg a tényleges keresendő elem meg nem található.

Miért van szükségünk bináris keresésre?

A következő okok miatt a bináris keresés jobb választás keresési algoritmusként való használatra:

• A bináris keresés hatékonyan működik rendezett adatokon, függetlenül az adatok méretétől
• Ahelyett, hogy a keresést úgy hajtaná végre, hogy sorozatban végigmenne az adatokon, a bináris algoritmus véletlenszerűen hozzáfér az adatokhoz, hogy megtalálja a kívánt elemet. Ez rövidebbé és pontosabbá teszi a keresési ciklusokat.
• A bináris keresés a rendezett adatok összehasonlítását rendezési elv alapján végzi el, mint az egyenlőségi összehasonlításokat, amelyek lassabbak és többnyire pontatlanok.
• Minden keresési ciklus után az algoritmus a tömb méretét felére osztja, így a következő iterációban csak a tömb fennmaradó felében fog működni

Tanuld meg a következő oktatóanyagunkat Lineáris keresés: Python, C++ Példa

Összegzésként

• A Keresés egy olyan segédprogram, amely lehetővé teszi a felhasználók számára, hogy dokumentumokat, fájlokat és más típusú adatokat keressenek. A bináris keresés egy speciális típusú keresési algoritmus, amely az elemek rendezett listájából talál meg és kér le adatokat.
• A bináris keresést általában félintervallumú keresésnek vagy logaritmikus keresésnek nevezik
• Úgy működik, hogy a tömböt félre osztja minden iterációnál, amely alatt a kívánt elem megtalálható.
• A bináris algoritmus a tömb közepét veszi úgy, hogy a bal és a jobb szélső indexértékek összegét elosztja 2-vel. Most az algoritmus az elemek alsó vagy felső korlátját ejti a tömb közepéről, attól függően, hogy melyik elemet kell találni.
• Az algoritmus véletlenszerűen hozzáfér az adatokhoz, hogy megtalálja a kívánt elemet. Ez rövidebbé és pontosabbá teszi a keresési ciklusokat.
• A bináris keresés a rendezett adatok összehasonlítását rendezési elv alapján végzi el, nem pedig lassú és pontatlan egyenlőségi összehasonlításokat.
• A bináris keresés nem alkalmas rendezetlen adatokhoz.