Mielőtt megtanulnánk a bináris keresést, tanuljuk meg:
Mi a Keresés?
A Keresés olyan segédprogram, amely lehetővé teszi a felhasználó számára, hogy dokumentumokat, fájlokat, adathordozókat vagy bármilyen más típusú adatot találjon az adatbázisban. A keresés azon az elven működik, hogy a kritériumokat összeegyeztetik a rekordokkal és megjelenítik 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 keresi meg az adatokat. Alapvető működési elve a felsorolásban szereplő adatok felére osztása, amíg a kívánt érték meg nem jelenik és megjelenik a felhasználó számára a keresési eredményben. A bináris keresést általában félidõs keresésként vagy logaritmikus keresésként ismerik .
Ebben az algoritmus-oktatóanyagban megtudhatja:
- Mi a Keresés?
- Mi az a bináris keresés?
- Hogyan működik a bináris keresés?
- Példa bináris keresésre
- Miért van szükség bináris keresésre?
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 adatsor középső elemének megkeresésével indul
- Ezt követően a kulcsértéket összehasonlítjuk az elemmel
- Ha a kulcs értéke kisebb, mint a középső elem, akkor a keresés elemzi a középső elem felső értékeit összehasonlítás és egyezés céljából
- Abban az esetben, ha a kulcsérték nagyobb, mint a középső elem, akkor a keresés elemzi az alsó értékeket a középső elemhez összehasonlítás és egyeztetés céljából
Példa bináris keresésre
Nézzük meg egy szótár példáját. Ha meg kell találnia egy bizonyos szót, akkor senki sem folytatja az egyes szavakat egymás után, hanem véletlenszerűen keresi meg a legközelebbi szavakat a kívánt szó kereséséhez.
A fenti kép a következőket szemlélteti:
- Tízjegyű tömbje van, és meg kell találni az 59 elemet.
- Az összes elemet 0 és 9 közötti index jelöli. Most kiszámoljuk a tömb közepét. Ehhez vegye az index bal és jobb szélső értékét, és ossza el 2-vel. Az eredmény 4,5, de mi a legalacsonyabb értéket vesszük. Ezért a közepe 4.
- Az algoritmus az összes elemet elesik a középsőtől (4) a legalacsonyabb határig, mert az 59 nagyobb, mint 24, és most a tömbnek csak 5 eleme van.
- Most 59 nagyobb, mint 45, és kevesebb, mint 63. A középső 7. Ezért a jobb index értéke középre válik - 1, ami egyenlő 6-mal, és a bal index értéke ugyanaz marad, mint korábban, ami 5.
- Ezen a ponton tudod, hogy 59 45 után következik. Ezért a bal oldali index, amely 5, szintén közepe lesz.
- Ezek az ismétlések addig folytatódnak, amíg a tömb csak egy elemre csökken, vagy a megtalált elem a tömb közepévé válik.
2. példa
Nézzük meg a következő példát, hogy megértsük a bináris keresés működését
- Rendezett értékek tömbje van 2 és 20 között, és 18-at kell megkeresnie.
- Az alsó és felső határ átlaga (l + r) / 2 = 4. A keresett érték nagyobb, mint a közepe, amely 4.
- A közepénél kisebb tömbértékek elhagyásra kerülnek a keresésből, és a 4-es középértéknél nagyobb értékeket keresnek.
- Ez egy ismétlődő felosztási folyamat, amíg a tényleges keresendő elem megtalálható.
Miért van szükség bináris keresésre?
A következő okok miatt a bináris keresés jobb választás a keresési algoritmusként való használatra:
- A bináris keresés hatékonyan működik a rendezett adatokon, az adatok méretétől függetlenül
- Ahelyett, hogy a keresést úgy végezné, hogy az adatokat szekvenciában végigjárja, a bináris algoritmus véletlenszerűen hozzáfér az adatokhoz, hogy megtalálja a szükséges elemet. Ezáltal a keresési ciklusok rövidebbek és pontosabbak.
- A bináris keresés a rendezett adatok összehasonlítását rendezési elv alapján hajtja végre, mint az egyenlőség-ö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
Összegzés
- A Keresés olyan segédprogram, amely lehetővé teszi a felhasználó számára, hogy dokumentumokat, fájlokat és más típusú adatokat keressen. A bináris keresés egy speciális típusú keresési algoritmus, amely az elemek rendezett listájából keresi meg az adatokat.
- A bináris keresést általában félidõs keresésként vagy logaritmikus keresésként ismerik
- Úgy működik, hogy a tömböt felére osztja minden iterációnál, a szükséges elem alatt.
- A bináris algoritmus a tömb közepét veszi úgy, hogy a bal és a jobb szélső index értékének összegét elosztja 2-gyel. Most az algoritmus az elemek alsó vagy felső határát eldobja a tömb közepétől, a megtalált elemtől függően. .
- Az algoritmus véletlenszerűen hozzáfér az adatokhoz, hogy megtalálják a szükséges elemet. Ezáltal a keresési ciklusok rövidebbek és pontosabbak.
- A bináris keresés a rendezett adatok összehasonlítását rendezési elv alapján hajtja végre, mint lassú és pontatlan egyenlőség-összehasonlításokat.
- A bináris keresés nem alkalmas nem rendezett adatokra.