Tartalomjegyzék:
Meghatározás - Mit jelent a bináris keresés?
Bináris keresési algoritmust használunk a rendezett tömbben található adott érték helyzetének megkeresésére. A szétválasztás és a meghódítás elvével együttműködve ez a keresési algoritmus meglehetősen gyors lehet, ám azzal a figyelmeztetéssel, hogy az adatoknak rendezett formában kell lennie. Úgy működik, hogy a keresést a tömb közepén indítja el, és a sorozat első alsó vagy felső részén lefelé halad. Ha a medián érték alacsonyabb, mint a célérték, ez azt jelenti, hogy a keresésnek magasabbra kell mennie, ha nem, akkor a tömb csökkenő részét kell megvizsgálnia.
A bináris keresést fél intervallum keresésnek vagy logaritmikus keresésnek is nevezik.
A Techopedia magyarázza a bináris keresést
A bináris keresés gyors és hatékony módszer egy meghatározott célérték megkeresésére a megrendelt elemek halmazából. A rendezett lista közepén kezdve hatékonyan felére csökkentheti a keresési helyet úgy, hogy meghatározza, hogy a listán a medián érték és a célértékhez viszonyítva emelkedik-e vagy csökken-e.
Például 8-as célértékkel és 1-11 közötti keresési területtel:
- Megtalálható a medián / középső érték, és a mutató ott van beállítva, amely ebben az esetben 6.
- A 8-os célt 6-hoz hasonlítják. Mivel a 6-nál kisebb, mint 8, a célnak a magasabb felében kell lennie.
- A mutatót a következő értékre (7) helyezik, és összehasonlítják a céllal. Ez kisebb, ezért a mutató a következő magasabb értékre lép.
- A mutató most 8. helyzetben van. Ha összehasonlítjuk ezt a céllal, akkor pontos egyezés, tehát a cél megtalálható.
A bináris keresés segítségével a célt csak három értékkel kellett összehasonlítani. Összehasonlítva egy lineáris kereséssel, az a legelső értéknél kezdődött volna, és felfelé haladt volna, és a célt nyolc értékre kellett hasonlítania. A bináris keresés csak rendezett adatkészlettel lehetséges; ha az adatok véletlenszerűen vannak elrendezve, akkor a lineáris keresés minden alkalommal eredményt ad, míg a bináris keresés valószínűleg beragad a végtelen hurokba.
