A lineáris keresés és a bináris keresés közötti fő különbség az, hogy a bináris keresés kevesebb időt vesz igénybe egy elem kereséséhez a rendezett elemek listájából. Tehát arra következtetünk, hogy a bináris keresési módszer hatékonysága nagyobb, mint a lineáris keresés.
Egy másik különbség a kettő között az, hogy a bináris keresés előfeltétele, azaz az elemeket sorba kell rendezni, míg a lineáris keresésben nincs ilyen előfeltétel. Bár mindkét keresési módszer különböző technikákat alkalmaz, amelyeket az alábbiakban tárgyalunk.
Összehasonlító táblázat
| Az összehasonlítás alapja | Lineáris keresés | Bináris keresés |
|---|---|---|
| Idő komplexitás | TOVÁBB) | O (log 2 N) |
| Legjobb esetben | Első O elem (1) | O Center Center Element (1) |
| Egy tömb előfeltétele | Nem szükséges | A tömbnek rendezett sorrendben kell lennie |
| Legrosszabb esetben az N számú elem | N összehasonlításra van szükség | Csak log 2 N összehasonlítás után tud következtetni |
| Alkalmazható | Array és Linked lista | Nem lehet közvetlenül a linkelt listán végrehajtani |
| Helyezze be a műveletet | Könnyen beilleszthető a lista végén | Szükséges a feldolgozás, hogy beilleszthesse a megfelelő helyre a rendezett lista fenntartásához. |
| Algoritmus típusa | Iteratív jellegű | Oszd meg és hódítsd meg a természetben |
| Hasznosság | Könnyen kezelhető és nincs szükség rendelt elemekre. | Bármilyen trükkös algoritmust és elemeket kell rendezni. |
| Kódsorok | Kevésbé | Több |
A lineáris keresés meghatározása
Egy lineáris keresés során a tömb minden egyes elemét egyenként, logikai sorrendben szerezzük be, és ellenőrizzük, hogy a kívánt elem vagy sem. A keresés sikertelen lesz, ha az összes elemet elérik, és a kívánt elem nem található. A legrosszabb esetben az átlagos eset számát meg kell vizsgálnunk a tömb méretének felét (n / 2).
Ezért a lineáris keresést úgy definiálhatjuk, mint azt a technikát, amely sorrendben áthalad a tömbön az adott tétel megkereséséhez. Az alábbi program illusztrálja a tömb elemének keresését a keresés segítségével.
A lineáris keresés hatékonysága
A keresési táblázatban a rekordok keresésekor elvégzett időfogyasztás vagy az összehasonlítások száma határozza meg a technika hatékonyságát. Ha a kívánt rekord a keresési táblázat első pozíciójában van, akkor csak egy összehasonlítás történik. Amikor a kívánt rekord az utolsó, akkor n összehasonlításra van szükség. Ha a rekordot a keresési táblázatban valahol be kell mutatni, akkor az összehasonlítások száma (n + 1/2) lesz. A technika legrosszabb hatékonysága O (n) a végrehajtás sorrendjét jelenti.
C Program olyan elem keresésére, amely lineáris keresési technikával rendelkezik.
#include #include void main () {int a [100], n, i, elem, loc = -1; clrscr (); printf ("Adja meg az elem számát:"); scanf ("% d", & n); printf ("Adja meg a számokat: n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("Adja meg a keresendő számot:"); scanf ("% d", & elem); (i = 0; i = 0) {printf ("n% d a (z)% d pozícióban található", elem, loc + 1); } else {printf ("Az elem nem létezik"); } getch (); } A bináris keresés meghatározása
A bináris keresés rendkívül hatékony algoritmus. Ez a keresési technika kevesebb időt vesz igénybe az adott tételben a lehető legkisebb összehasonlításban. A bináris kereséshez először rendezni kell a tömbelemeket.
Az alábbi technika logikája a következő:
- Először keresse meg a tömb középső elemét.
- A tömb középső elemét a keresendő elemhez hasonlítjuk.
Három eset fordulhat elő:
- Ha az elem a szükséges elem, akkor a keresés sikeres.
- Ha az elem kisebb, mint a kívánt elem, akkor csak a tömb első felét keressük.
- Ha nagyobb, mint a kívánt elem, akkor keresse meg a tömb második felét.
Ismételje meg ugyanazt a lépést, amíg egy elemet nem talál, vagy kimerül a keresési területen. Ebben az algoritmusban a keresési terület minden alkalommal csökken. Ezért az összehasonlítások száma legfeljebb log (N + 1). Ennek eredményeként ez egy hatékony algoritmus a lineáris kereséshez képest, de a tömböt a bináris keresés előtt kell rendezni.
C Programozza meg a bináris keresési technikával rendelkező elemet.
#include void main () {int i, beg, end, közép, n, keresés, tömb [100]; printf ("Adja meg az elem számát"); scanf ( "% d", és n); printf ("Adja meg a% d számokat n", n); (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Adja meg a keresendő számot"); scanf ("% d" és keresés); beg = 0; end = n - 1; középső = (beg + end) / 2; míg (beg <= end) {if (array [middle] end) printf ("A keresés sikertelen!% d nem szerepel a listában. \ t getch (); } A lineáris keresés és a bináris keresés legfontosabb különbségei
- A lineáris keresés a természetben ismétlődő és szekvenciális megközelítést alkalmaz. Másrészről a bináris keresés végrehajtja a megosztási és hódító megközelítést.
- A lineáris keresés időkomplexitása O (N), míg a bináris keresés O (log 2 N).
- A lineáris keresés legjobb esete az első elem, azaz O (1). A bináris keresésnél a középső elem, azaz O (1).
- A lineáris keresésben az elem keresésének legrosszabb esete az N szám. Ezzel szemben a bináris keresés log 2 N számának összehasonlítása.
- A lineáris keresés végrehajtható egy tömbben, valamint a csatolt listában, míg a bináris keresés nem valósítható meg közvetlenül a kapcsolt listán.
- Mint tudjuk, a bináris keresés megköveteli a rendezett tömböt, ami az oka. Feldolgozásra van szükség ahhoz, hogy a megfelelő helyre helyezze be a rendezett listát. Éppen ellenkezőleg, a lineáris keresés nem igényel válogatott elemeket, így az elemek könnyen beilleszthetők a lista végén.
- A lineáris keresés könnyen használható, és nincs szükség rendelt elemekre. Másrészről azonban a bináris keresési algoritmus trükkös, és az elemek szükségszerűen rendezettek.
Következtetés
Mind a lineáris, mind a bináris keresési algoritmusok hasznosak lehetnek az alkalmazástól függően. Ha egy tömb az adatszerkezet és az elemek rendezett sorrendben vannak elrendezve, akkor a gyorskeresésnél előnyösebb a bináris keresés. Ha a kapcsolt lista az adatszerkezet, függetlenül attól, hogy az elemek hogyan vannak elrendezve, a lineáris keresést a bináris keresési algoritmus közvetlen megvalósításának hiánya miatt fogadják el.
A tipikus bináris keresési algoritmus nem használható a kapcsolt listára, mert a linkelt lista dinamikus jellegű, és nem ismert, hogy a középső elem ténylegesen hozzárendelt-e. Ezért van szükség a bináris keresési algoritmus variációjának megtervezésére is, mivel a bináris keresés gyorsabb a végrehajtásnál, mint a lineáris keresés.
