Bináris keresés a Pythonban: Vizuális bevezetés

Üdvözöljük

Ebben a cikkben megtudhatja, hogyan működik a bináris keresés algoritmus a kulisszák mögött, és hogyan tudja megvalósítani a Pythonban.

Különösen megtanulja:

• Hogyan működik az algoritmus a színfalak mögött, hogy megtalálja a célelemet.
• Hogyan működik Python-implementációja soronként.
• Miért nagyon hatékony algoritmus a lineáris kereséshez képest?
• Előnyei és követelményei.

Kezdjük! ✨

? Bevezetés a bináris keresésbe

Ezt az algoritmust arra használják, hogy egy rendezett sorrendben elemet találjon (például: listát, duplát vagy karakterláncot).

Követelmények

A bináris keresési algoritmus szekvenciához való alkalmazásához a szekvenciát már növekvő sorrendben kell rendezni. Ellenkező esetben az algoritmus nem fogja megtalálni a helyes választ. Ha mégis megtörténik, akkor véletlenszerűen történik.

? Tipp: A bináris keresés alkalmazása előtt rendezheti a sorrendet az Ön igényeinek megfelelő rendezési algoritmussal.

Bemenet és kimenet

A függvényként megvalósított algoritmusnak szüksége van ezekre az adatokra:

• Rendezett elemsorozat (például: lista, páros, karakterlánc).
• A keresett célelem.

Visszaadja a keresett elem indexét , ha megtalálható. Ha az elem nem található, akkor -1 adódik vissza.

Hatékonyság

Nagyon hatékony a lineáris kereséshez képest (elem keresése egyesével, az elsőtől kezdve), mert minden lépésnél képesek vagyunk a lista felét "elvetni".

Kezdjük el merülni ezt az algoritmust.

? Visual Walkthrough

A Binary Search algoritmust erre a listára alkalmazzuk:

? Tipp: Vegye figyelembe, hogy a lista már rendezve van. Az indexeket vizuális referenciaként tartalmazta.

Cél

Meg akarjuk találni a 67 egész indexét .

Intervallum

Tegyünk úgy, mintha mi lennénk az algoritmus. Hogyan kezdjük el a folyamatot?

Kezdjük azzal, hogy kiválasztjuk az intervallum két határát, ahol keresni akarunk. Meg akarjuk keresni a teljes listát, ezért 0alsó indexként 5az indexet , felső határként pedig az indexet választjuk :

Középső elem

Most meg kell találnunk a középső elem indexét ebben az intervallumban. Ezt úgy tesszük, hogy összeadjuk az alsó és a felső határt, és az eredményt elosztjuk 2-vel egész osztás segítségével.

Ebben az esetben (0 + 5)//2is 2, mert az eredmény 5/2az, 2.5és osztás levágja a tizedes rész.

Tehát a középső elem a 2. indexen található , a középső elem pedig a 6. szám :

Összehasonlítások

Most el kell kezdenünk összehasonlítani a középső elemet a célelemmel, hogy lássuk, mit kell tennünk ezután.

Kérünk:

A középső elem megegyezik-e azzal az elemmel, amelyet keresünk?

6 == 67 # False

Nem, nem az.

Tehát azt kérdezzük:

A középső elem nagyobb, mint a keresett elem?

6 > 67 # False

Nem, nem az.

Tehát a középső elem kisebb, mint a keresett elem.

6 < 67 # True

Elveti az elemeket

Mivel a lista már rendezve van, ez valami rendkívül fontosat mond nekünk. Azt mondja nekünk, hogy "eldobhatjuk" a lista alsó felét, mert tudjuk, hogy az összes elem, amely a középső elem elé kerül, kisebb lesz, mint a keresett elem, tehát a célelemünk nincs ott.

Újrakezdés - Válassza ki a határokat

Mi lesz a következő, amit csinálunk? Elvetettük az elemeket, és a ciklus ismétlődik.

Meg kell választanunk az új intervallum határait (lásd alább). De vegye figyelembe, hogy a felső határ sértetlen marad, és csak az alsó határ változik meg.

Ennek oka, hogy a keresett elem a lista felső felében lehet. A felső határt érintetlenül tartják, és az alsó határt megváltoztatják, hogy "összezsugorítsák" az intervallumot egy olyan intervallumra, ahol a célelemünk megtalálható.

? Tipp: Ha a középső elem nagyobb lett volna, mint a keresett elem, akkor a felső határ megváltozott, és az alsó határ érintetlen maradt. Így elvetnénk a lista felső felét, és folytatnánk a keresést az alsó felében.

Középső elem

Most meg kell találnunk a középső elem indexét úgy, hogy hozzáadjuk az alsó határt a felső határhoz, és az eredményt elosztjuk 2-vel egész osztás segítségével.

Az eredmény (3+5)//2az 4, hogy a középső elem az indexen található, 4a középső pedig 67 .

Összehasonlítások

Kérünk:

A középső elem megegyezik-e azzal az elemmel, amelyet keresünk?

67 == 67 # True

Igen, ez az! Tehát megtaláltuk az elemet a 4. indexen . A 4. érték visszaadódik, és az algoritmus sikeresen befejeződött.

? Tipp: Ha az elemet nem találták meg, a folyamat addig folytatódott, amíg az intervallum már nem volt érvényes. Ha az elemet nem találták meg a teljes listában, akkor -1-et adtak volna vissza.

? Kód áttekintés

Most, hogy van egy vizuális megérzése arról, hogy az algoritmus hogyan működik a színfalak mögött, merüljünk el az iteratív Python megvalósításba soronkénti elemzéssel:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Fejléc

Itt van a függvény fejléc:

def binary_search(data, elem):

Két érvre van szükség:

• Az elemek sorrendje (például: lista, páros vagy karakterlánc).
• Az elem, amelyet meg akarunk találni.

Kezdeti időköz

A következő sor meghatározza a kezdeti alsó és felső határt:

low = 0 high = len(data) - 1

A kezdeti alsó határ index 0, a kezdeti felső határ pedig a sorozat utolsó indexe.

Hurok

Megismételjük a folyamatot, amíg érvényes időköz van, míg az alsó határ kisebb vagy egyenlő a felső határral.

while low <= high:

? Tipp: Ne feledje, hogy a határok indexek.

Középső elem

Minden iterációnál meg kell találnunk a középső elem indexét. Ehhez hozzáadjuk az alsó és a felső határt, és az eredményt elosztjuk 2-vel egész osztás segítségével.

middle = (low + high)//2

? Tipp: Egész számfelosztást használunk, ha a lista vagy intervallum páros számú elemet tartalmaz. Például, ha a lista már 6 elemeket és nem használtuk osztás, middlelenne az eredménye (0 + 5)/2, ami 2.5. Az index nem lehet lebegő, ezért megcsonkítjuk a tizedes részt a használatával, //és kiválasztjuk az elemet az indexen 2.

Összehasonlítások

Ezekkel a feltételekkel (lásd alább) a középső elem értékétől függően határozzuk meg, hogy mit tegyünk data[middle]. Összehasonlítjuk a keresett célelemmel.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Három lehetőség van:

• Ha a középső elem megegyezik a keresett elemmel, akkor azonnal visszaadjuk az indexet, mert megtaláltuk az elemet.

if data[middle] == elem: return middle

• Ha a középső elem nagyobb, mint a keresett elem, akkor hozzárendeljük a felső határt, mert tudjuk, hogy a célelem a lista alsó felében található.

elif data[middle] > elem: high = middle - 1

• Egyébként az egyetlen lehetőség megmaradt, hogy a középső elem kisebb, mint a keresett elem, ezért az alsó határt újból kijelöljük, mert tudjuk, hogy a célelem a lista felső felében található.

else: low = middle + 1

Az elem nem található

Ha a ciklus az elem megkeresése nélkül fejeződik be, akkor a -1 értéket adja vissza.

return -1

és megvan a Bináris keresés algoritmus végleges megvalósítása:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

? Különleges esetek

Íme néhány olyan különleges eset, amelyet az algoritmus használatának megkezdése során találhat meg:

Ismételt elemek

Ha a keresett elem megismétlődik a szekvenciában, a visszaküldött index az elemek számától és az algoritmus által a szekvencián végrehajtott műveletsorozattól függ.

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

Az elem nem található

Ha az elem nem található, akkor -1 adódik vissza.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Üres szekvencia

Ha a sorozat üres, -1-et adunk vissza.

>>> b = [] >>> binary_search(b, 8) -1

Válogatás nélküli sorrend

Ha a sorrend nincs rendezve, akkor a válasz nem lesz helyes. A helyes index megszerzése tiszta véletlen, és annak oka lehet az elemek sorrendje a sorrendben és az algoritmus által végrehajtott műveletek sorrendje.

Ez a példa a helyes eredményt adja vissza:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

De ez nem:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

? Tipp: Gondolja át, miért adja vissza az első példa a helyes eredményt. Tipp: Pontos véletlen, hogy az elemek sorrendje miatt az algoritmus eléri a helyes indexet, de a lépésenkénti folyamat kiértékeli 0, majd 2végül 6. Ebben a konkrét esetben az adott elem esetében a megfelelő index akkor is megtalálható, ha a sorrend nincs rendezve.

? Összetettebb példa

Most, hogy jobban ismeri az algoritmust és annak Python-implementációját, itt van egy összetettebb példa:

A bináris keresés segítségével meg akarjuk találni a 45 elem indexét ebben a listában:

Első iteráció

Az alsó és a felső határ kiválasztása:

A középső elem ( 26 ) van kiválasztva:

De a középső elem ( 26 ) nem az az elem, amelyet keresünk, kisebb, mint 45 :

Második iteráció

Így eldobhatunk minden elemet, amely kisebb, mint a középső elem, és új határokat választhatunk ki. Az új alsó határ ( 27 ) az előző középső elemtől jobbra található elem:

? Tipp: Ne feledje, hogy a lista már rendezve van.

Az új középső elem ( 30 ) van kiválasztva:

A középső ( 30 ) elem nem az az elem, amelyet keresünk, kisebb, mint 45 :

Harmadik iteráció

A 30- nál kisebb vagy azzal egyenlő elemeket eldobhatjuk, amelyeket még nem dobtak el. Az alsó határérték 32-re frissül :

Itt van egy érdekes esetünk: a középső elem az aktuális intervallum egyik határa, mert (7+8)//2az 7.

A középső ( 32 ) elem nem az az elem, amelyet keresünk ( 45 ), hanem kisebb.

Negyedik iteráció

A 32- nél kisebb vagy azzal egyenlő elemeket eldobhatjuk, amelyeket még nem dobtak el.

Itt van egy másik nagyon érdekes esetünk: az intervallumnak csak egy eleme van.

? Tipp: Ez az intervallum azért érvényes, mert ezt a feltételt írtuk while high <= low:, amely olyan intervallumokat tartalmaz, amelyekben az alsó határ indexe megegyezik a felső határ indexével.

A középső elem az egyetlen elem az intervallumban, mert így (8+8)//2van 8, tehát a középső elem mutatója 8 , a középső pedig 45 .

Most a középső elem az az elem, amelyet keresünk, 45 :

Tehát a 8. érték (az index) visszatér:

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

? Extra gyakorlat

Ha szeretne még egy kis gyakorlatot ezzel az algoritmussal, próbálja meg elmagyarázni, hogyan működik az algoritmus a színfalak mögött, amikor ezt a listát alkalmazza a 90-es egész szám megkeresésére :

[5, 8, 15, 26, 38, 56]

• Mi történik lépésről lépésre?
• Milyen értéket adunk vissza?
• Megtalálták az elemet?

Nagyon remélem, hogy tetszett a cikkem, és hasznosnak találta. Most megvalósíthatja a bináris keresés algoritmust a Pythonban. Nézze meg a "Python keresési és rendezési algoritmusok: gyakorlati megközelítés" című online tanfolyamomat. Kövess a Twitteren. ⭐️