Tartalom

• Összehasonlító táblázat
• A lineáris keresés meghatározása
• A bináris keresés meghatározása
• Következtetés

A lineáris keresés és a bináris keresés a két módszer, amelyeket a tömbökben használnak keresés az elemek. A keresés egy elem megkeresésének eleme az elemek listájában, bármilyen sorrendben vagy véletlenszerűen tárolva.

A fő különbség a lineáris és a bináris keresés között az, hogy a bináris keresés kevesebb időt vesz igénybe egy elem kiválasztott elemlistájából. Tehát arra lehet következtetni, 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ésnek előfeltétele van, azaz az elemeknek meg kell lenniük kiválogatott 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.

1. Összehasonlító táblázat
2. Meghatározás
3. Főbb különbségek
4. Következtetés

Összehasonlító táblázat

Az összehasonlítás alapja	Lineáris keresés	Bináris keresés
Idő komplexitása	TOVÁBB)	O (log 2 N)
A legjobb eset	Első elem O (1)	Középső elem O (1)
A tömb előfeltétele	Nem szükséges	A tömbnek rendezett sorrendben kell lennie
A legrosszabb eset az N számú elem esetében	N nem szükséges összehasonlítás	Csak log után tud következtetni2N összehasonlítás
Meg lehet valósítani	Tömb és kapcsolódó lista	Nem lehet közvetlenül végrehajtani a csatolt listán
Helyezze be a műveletet	Könnyen beilleszthető a lista végére	A rendezett lista karbantartása érdekében feldolgozásra van szükség, hogy beszúrja a megfelelő helyre.
Algoritmus típusa	Iteratív jellegű	Ossza meg és meghódítsa a természetben
Hasznosság	Könnyen kezelhető, és nincs szükség megrendelt elemekre.	Mindenesetre trükkös algoritmust és elemeket sorrendbe kell rendezni.
Kód vonalai	Kevésbé	Több

A lineáris keresés meghatározása

Lineáris keresés során a tömb minden elemét lekérdezzük logikai sorrendben, és ellenőrizzük, hogy a kívánt elem vagy sem. A keresés sikertelen lesz, ha az összes elemhez hozzáférnek, és a kívánt elem nem található. A legrosszabb esetben az átlagos eset számát a tömb méretének felére (n / 2) kell leolvasni.

Ezért a lineáris keresés úgy definiálható, mint az a technika, amely a tömböt egymás után haladja át, hogy megkeresse az adott elemet. Az alábbiakban bemutatott program a tömb egy elemének kereséssel történő keresését szemlélteti.

Hatékonyság lineáris keresés

A keresési táblázatban egy rekord keresésével végzett időigény vagy összehasonlítások száma meghatározza 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ást végeznek. Ha a kívánt rekord az utolsó, akkor n összehasonlítást kell végezni. Ha a rekordnak valahol a keresési táblázatban kell szerepelnie, az összehasonlítások száma átlagosan (n + 1/2) lesz. Ennek a technikanak a legrosszabb hatékonysága az O (n), a végrehajtás sorrendjét jelenti.

C Program elem kereséséhez lineáris keresési technikával.

#include #include void main () {int a, n, i, item, loc = -1; clrscr (); f (" n Adja meg az elem számát:"); scanf ("% d", & n); f ("Írja be a számokat: n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nÍrja be a keresendő számot:"); scanf ("% d", & elem); for (i = 0; i <= n-1; i ++) {if (tétel == a) {loc = i; szünet; }} if (loc> = 0) {f (" n% d található a% d pozícióban:", tétel, loc + 1); } else {f (" n 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 elem keresésében a lehető legkevesebb összehasonlítás mellett. A bináris kereséshez először a tömb elemeit kell rendezni.

A technika mögötti logika az alábbiakban olvasható:

• Először keresse meg a tömb középső elemét.
• A tömb középső elemét összehasonlítják a keresendő elemmel.

Három eset fordulhat elő:

1. Ha az elem a szükséges elem, akkor a keresés sikeres.
2. Ha az elem kevesebb, mint a kívánt elem, akkor csak a tömb első felében keressen.
3. Ha ez nagyobb, mint a kívánt elem, akkor keresse meg a tömb második felét.

Ismételje meg ugyanazokat a lépéseket, amíg egy elem meg nem található vagy kimerül a keresési területen. Ebben az algoritmusban minden alkalommal csökken a keresési terület. Ezért az összehasonlítások száma legfeljebb log (N + 1). Ennek eredményeként hatékony algoritmus a lineáris kereséshez viszonyítva, de a tömböt a bináris keresés megkezdése előtt meg kell rendezni.

C Program egy elem kereséséhez bináris keresési technikával.

#include void main () {int i, beg, end, middle, n, keresés, tömb; f ("Írja be az elem számát n"); scanf ( "% d", és n); f ("Írja be a% d számokat n", n); (i = 0; i <n; i ++) scanf ("% d", és tömb); f ("Írja be a keresendõ számot n"); scanf ("% d", és keresés); beg = 0; vége = n - 1; középső = (beg + vége) / 2; while (beg <= vége) {if (tömb <keresés) beg = middle + 1; egyébként, ha (tömb == keresés) {f ("A keresés sikeres. n% d található a% d helyen. n", keresés, középső + 1); szünet; } másik vége = középső - 1; középső = (beg + vége) / 2; } if (beg> end) f ("A keresés sikertelen!% d nincs jelen a listában. n", keresés); getch (); }

1. A lineáris keresés iteratív jellegű és szekvenciális megközelítést alkalmaz. Másrészt a bináris keresés megosztási és hódítási megközelítést valósít meg.
2. A lineáris keresés időbeli összetettsége O (N), míg a bináris keresés O (log₂N).
3. A legjobb eset a lineáris keresésben az első elemre, azaz az O (1) -re. Ezzel szemben a bináris keresésben a középső elemre, azaz O (1) -re vonatkozik.
4. A lineáris keresés során az elem keresésekor a legrosszabb eset az N összehasonlítás száma. Ezzel szemben log₂N összehasonlítás száma a bináris keresésnél.
5. A lineáris keresés tömbben és összekapcsolt listában is megvalósítható, míg a bináris keresés nem hajtható végre közvetlenül a csatolt listán.
6. Mint tudjuk, a bináris kereséshez szükség van a rendezett tömbre, amely indokolt. A rendezett lista fenntartása érdekében feldolgozást kell végrehajtania a megfelelő helyre való beszúráshoz. Ezzel szemben a lineáris keresés nem igényel rendezett elemeket, így az elemek könnyen beilleszthetők a lista végére.
7. A lineáris keresést könnyű használni, és nincs szükség megrendelt elemekre. Másrészt a bináris keresési algoritmus azonban trükkös, és az elemek szükségszerűen sorrendben vannak elrendezve.

Következtetés

Mind a lineáris, mind a bináris keresési algoritmus hasznos lehet az alkalmazástól függően. Ha egy tömb az adatszerkezet, és az elemek rendezett sorrendben vannak elrendezve, akkor a bináris keresést részesítjük előnyben gyorskeres. Ha a csatolt lista az adatstruktúra, az elemek elrendezésétől függetlenül, akkor 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 algoritmust nem lehet felhasználni a csatolt listára, mivel a kapcsolt lista jellegű dinamikus, és nem ismert, hogy a középső elem valójában hol van hozzárendelve. Ezért szükség van a bináris keresési algoritmus variációjának megtervezésére, amely képes működni a kapcsolt listán is, mivel a bináris keresés gyorsabban hajtható végre, mint egy lineáris keresés.