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. Meghatározott értéket keres a listában a lista minden elemének ellenőrzésével. A bináris keresés egy módszer arra is szolgál, hogy egy megadott értéket keressen egy rendezett listában. A bináris keresési módszer felére csökkenti az ellenőrzött elemek számát (minden egyes iterációban), ezzel csökkentve az adott tétel felsorolásához szükséges időt.
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 megadott elemet. A lineáris keresési módszer bemenete egy szekvencia (például tömb, gyűjtemény vagy karakterlánc) és az elem, amelyre keresni kell. A kimenet igaz, ha a megadott elem a megadott sorrendben van, vagy hamis, ha nem a sorrendben van. Mivel ez a módszer addig ellenőrzi a lista minden elemét, amíg a megadott elem megtalálható, a legrosszabb esetben a lista összes elemét végigjárja, mielőtt megtalálja a szükséges elemet. A lineáris keresés bonyolultsága o (n). Ezért túl lassúnak tekinthető, ha nagy listákban keresünk elemeket. De ez nagyon egyszerű és könnyebben megvalósítható.
Mi az a bináris keresés?
A bináris keresés egy módszer arra is szolgál, hogy egy adott elemet egy rendezett listában keressen meg. Ez a módszer azzal kezdődik, hogy összehasonlítja a keresett elemet a lista közepén található elemekkel. Ha az összehasonlítás megállapítja, hogy a két elem egyenlő, akkor a módszer leáll és visszaadja az elem helyzetét. Ha a keresett elem nagyobb, mint a középső elem, akkor a rendezett lista alsó felét használva újrakezdi a módszert. Ha a keresett elem kevesebb, mint a középső elem, akkor a rendezett lista legfelső felét használva indítja újra a módszert. Ha a keresett elem nincs a listán, a módszer egyedi értéket ad vissza, jelezve ezt. Ezért a bináris keresési módszer felére csökkenti az összehasonlított elemek számát (minden egyes iterációban), az összehasonlítás eredményétől függően. Következésképpen,a bináris keresés logaritmikus időben fut, ami o (log n) átlagos eset teljesí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 keresés és a bináris keresés is keresési módszer, számos különbség van. Míg a bináris keresés rendezett listákon működik, addig a vonalas keresés válogatás nélküli listákon is működhet. A lista rendezésének átlagos esetösszetétele n log n. a lineáris keresés egyszerűen és egyszerűen megvalósítható, mint a bináris keresés. De a lineáris keresés túl lassú ahhoz, hogy nagy listákkal használható legyen o (n) átlagos eset teljesítménye miatt. Másrészt a bináris keresést hatékonyabb módszernek tekintik, amelyet nagy listákkal lehetne használni. 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.
