Különbség a bináris keresés és a lineáris keresés között

Bináris keresés vs. Lineáris keresés

A lineáris keresés, más néven a szekvenciális keresés a legegyszerűbb keresési algoritmus. Meghatározott értéket keres egy listában a lista minden elemének ellenőrzésével. A bináris keresés egy módszer is arra, hogy egy meghatározott értéket megtaláljon a 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 listában történő megkereséséhez 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 egyes elemeit egymás után ellenőrzi, amíg meg nem találja a megadott elemet. A lineáris keresési módszer bemenete egy szekvencia (például egy tömb, gyűjtemény vagy egy karakterlánc) és a keresendő elem. A kimenet akkor igaz, ha a megadott elem a megadott sorozaton belül van, vagy hamis, ha nem a sorozatban. Mivel ez a módszer ellenőrzi a lista minden elemét, amíg a megadott elem meg nem található, a legrosszabb esetben a lista összes elemén átmegy, mielőtt megtalálja a kívánt elemet. A lineáris keresés bonyolultsága o (n). Ezért túl lassúnak tartják azt, amikor elemeket keresnek a nagy listákban. De ez nagyon egyszerű és könnyebben megvalósítható.

Mi a bináris keresés??

A bináris keresés egy olyan módszer is, amelyet egy adott elemnek a rendezett listában történő megkeresésére használnak. Ez a módszer azzal kezdődik, hogy a keresett elemet összehasonlítjuk a lista közepén lévő 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 újra elindítja a módszert, csak a rendezett lista alsó felét használva. Ha a keresett elem kisebb, mint a középső elem, akkor újra elindítja a módszert, csak a rendezett lista felső felét használva. Ha a keresett elem nem található a listán, akkor a módszer egy egyedi értéket ad vissza, amely ezt jelzi. Ezért a bináris keresési módszer felére csökkenti az összehasonlított elemek számát (minden 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, o (log n) átlagos esetteljesítményt eredményezve.

Mi a különbség a bináris keresés és a lineáris keresés között?

Annak ellenére, hogy mind a lineáris, mind a bináris keresés keresési módszerek, számos különbségük van. Míg a bináris keresés válogatott listákon működik, addig a vonalhajózási keresés nem válogatott listákon is működhet. A lista rendezésekor az esetek átlagos bonyolultsága n log n. A lineáris keresés egyszerű és érthető, mint a bináris keresés. De a lineáris keresés túl lassú ahhoz, hogy nagy listákkal lehessen használni, o (n) esetének átlagos teljesítménye miatt. Másrészt a bináris keresést hatékonyabb módszernek tekintik, amelyet nagy listákhoz lehet használni. A bináris keresés végrehajtása azonban 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..