Lineáris és bináris keresési algoritmusok magyarázata

Az adatok keresésének lehetősége az informatika egyik fontos eleme. A keresési algoritmusok egy adott elem keresésére szolgálnak az adathalmazban.

Az algoritmusok logikai eredményt adnak vissza (igaz vagy hamis) a keresési lekérdezéshez. Ezeket módosítani is lehet, hogy megadják a talált érték relatív helyzetét.

Ebben a cikkben az algoritmusok annak meghatározására összpontosítanak, hogy létezik -e érték.

Lineáris keresési algoritmusok

A lineáris keresést szekvenciális keresésnek is nevezik. Az ilyen típusú kereséseknél a lista minden egyes értékét rendre felkeresik, miközben ellenőrzik, hogy létezik -e a kívánt érték.

Az algoritmus értékenként ellenőrzi az értéket, amíg meg nem találja a keresett értéket, vagy elfogy a keresendő érték. Ha elfogynak a keresendő értékek, ez azt jelenti, hogy a keresési lekérdezés nem létezik a listában.

A szekvenciális keresési algoritmus az értékek listáját és a lista kívánt elemét veszi paraméterként. A visszaküldési eredmény inicializálva van Hamis és át fog változni Igaz amikor megtalálta a kívánt értéket.

Példaként lásd az alábbi Python implementációt:

def linearSearch (mylist, item):

talált = hamis

index = 0

míg az index

ha a listám [index] == elem:

talált = Igaz

más:

index = index+1

visszatérés megtalálható

Algoritmus elemzés

A legjobb eset akkor fordul elő, ha a kívánt elem az első a listán. A legrosszabb eset akkor fordul elő, ha a kívánt elem az utolsó a listán (az n. Tétel). Ezért a lineáris keresés időbeli összetettsége O (n).

A fenti algoritmus átlagos eset forgatókönyve n/2.

Összefüggő: Mi az a Big-O jelölés?

Módosított lineáris keresés

Fontos tudni, hogy az alkalmazott algoritmus feltételezi, hogy az elemek véletlenszerű listája biztosított. Vagyis a listaelemek nincsenek külön sorrendben.

Tegyük fel, hogy a tételek meghatározott sorrendben voltak, mondjuk a legkisebbtől a legnagyobbig. Lehetséges lenne valamilyen előnyt elérni a számításban.

Vegyünk egy példát arra, hogy a megadott listában 19 -et keresünk: [2, 5, 6, 11, 15, 18, 23, 27, 34]. A 23 év elérése után világossá válik, hogy a keresett elem nem létezik a listában. Ezért már nem lenne fontos folytatni a lista többi elemének keresését.

Bináris keresési algoritmusok

Látta, hogy a rendezett lista hogyan csökkentheti a szükséges számítást. A bináris keresési algoritmus még jobban kihasználja ezt a hatékonyságot, amit a rendezett lista vezet be.

Az algoritmus azzal kezdődik, hogy a rendezett lista középső értékét veszi, és ellenőrzi, hogy ez a kívánt érték. Ha nem, akkor az érték ellenőrzi, hogy kisebb vagy nagyobb, mint a kívánt érték.

Ha kevesebb, akkor nincs szükség a lista alsó felének ellenőrzésére. Ellenkező esetben, ha nagyobb, akkor a lista felső felére lép.

Összefüggő: Mi a rekurzió és hogyan kell használni?

Függetlenül attól, hogy melyik allistát választja (bal vagy jobb), a középső érték ismét meghatározásra kerül. Az értéket ismét ellenőrzi, ha ez a szükséges érték. Ha nem, akkor ellenőrzik, hogy kisebb vagy nagyobb, mint a kért érték.

Ezt a folyamatot addig ismételjük, amíg meg nem találjuk az értéket.

Az alábbi Python implementáció a bináris keresési algoritmusra vonatkozik.

def binarySearch (mylist, item):

alacsony = 0

magas = len (mylist) - 1

talált = hamis

míg alacsony <= magas és nem található:

közép = (alacsony + magas) // 2

ha a listám [közepes] == elem:

talált = Igaz

elif item

magas = közepes - 1

más:

alacsony = közepes + 1

visszatérés megtalálható

Algoritmus elemzés

A legjobb eset akkor fordul elő, ha a kívánt elem a középső elem. A legrosszabb forgatókönyv azonban nem ilyen egyszerű. Kövesse az alábbi elemzést:

Az első összehasonlítás után n/2 elem marad. A második után n/4 elem marad. A harmadik után n/8.

Figyeljük meg, hogy az elemek száma a felére csökken, amíg el nem éri az n/2i értéket, ahol i az összehasonlítások száma. Az összes felosztás után végül csak 1 tételt kapunk.

Ez magában foglalja:

n/2i = 1

Ezért a bináris keresés O (log n).

Tovább a rendezéshez

A bináris keresésben olyan esetet vettünk figyelembe, amikor az adott tömb már el volt rendelve. De tegyük fel, hogy rendetlen adatkészlete volt, és bináris keresést akart végrehajtani rajta. Mit csinálnál?

A válasz egyszerű: rendezze. Az informatikában számos válogatási technika létezik, amelyeket jól kutattak. Az egyik ilyen technika, amelyet elkezdhet tanulmányozni, a kiválasztási rendezés algoritmusa, miközben rengeteg útmutatót találunk más területekhez is.

A kiválasztási rendezés használata

A kiválasztási módot kezdőknek kissé bonyolult megérteni, de nem túl nagy kihívás, ha megkapjuk a dolgok lendületét.

Olvassa tovább

A szerzőről