Bináris keresés vs lineáris keresés
A lineáris keresés, más néven szekvenciális keresés a legegyszerűbb keresési algoritmus. Egy listában egy megadott értéket keres a lista minden elemének ellenőrzésével. A bináris keresés egy olyan módszer is, amelyet egy meghatározott érték megkeresésére használnak egy rendezett listában. A bináris keresési módszer felére csökkenti az ellenőrzött elemek számát (minden iterációban), csökkentve az adott elem megtalálásához szükséges időt a listában.
Mi az a lineáris keresés?
A lineáris keresés a legegyszerűbb keresési módszer, amely a lista minden elemét egymás után ellenőrzi, amíg meg nem talál egy adott elemet. A lineáris keresési módszer bemenete egy sorozat (például egy tömb, gyűjtemény vagy egy karakterlánc) és a keresendő elem. A kimenet igaz, ha a megadott elem a megadott sorozaton belül van, vagy hamis, ha nincs a sorozatban. Mivel ez a módszer a lista minden elemét ellenőrzi, amíg a megadott elemet meg nem találja, a legrosszabb esetben a lista összes elemét végigmegy, mielőtt megtalálná a kívánt elemet. A lineáris keresés összetettsége o(n). Ezért túl lassúnak tekinthető ahhoz, hogy nagy listákban keressen elemeket. De ez nagyon egyszerű és könnyebben megvalósítható.
Mi az a bináris keresés?
A bináris keresés egy olyan módszer is, amelyet egy meghatározott elem megkeresésére használnak egy rendezett listában. Ez a módszer a keresett elem és a lista közepén lévő elem összehasonlításával kezdődik. Ha az összehasonlítás megállapítja, hogy a két elem egyenlő, a metódus leáll, és visszaadja az elem pozícióját. Ha a keresett elem nagyobb, mint a középső elem, akkor újraindítja a metódust, csak a rendezett lista alsó felét használva. Ha a keresett elem kisebb, mint a középső elem, akkor újraindítja a metódust, csak a rendezett lista felső felét használva. Ha a keresett elem nem szerepel a listán, a metódus egyedi értéket ad vissza, jelezve ezt. Ezért a bináris keresési módszer az összehasonlítás eredményétől függően felére csökkenti az összehasonlított elemek számát (minden iterációban). Következésképpen a bináris keresés logaritmikus időben fut, ami o(log n) átlagos esetteljesítményt eredményez.
Mi a különbség a bináris keresés és a lineáris keresés között?
Annak ellenére, hogy a lineáris és a bináris keresés is keresési módszerek, számos különbség van. Míg a bináris keresés rendezett listákon működik, a vonalas keresés a rendezetlen listákon is működhet. A lista rendezésének átlagos esetkomplexitása általában n log n. A lineáris keresés egyszerűbb és egyszerűbb megvalósítani, mint a bináris keresés. Ám a lineáris keresés túl lassú ahhoz, hogy nagy listákkal lehessen használni, o(n) átlagos esetteljesítménye miatt. Másrészt a bináris keresés hatékonyabb módszernek tekinthető, amely nagy listák esetén is használható. De a bináris keresés megvalósítása meglehetősen bonyolult lehet, és egy tanulmány kimutatta, hogy a bináris keresés pontos kódja húsz könyvből csak ötben található meg.
