A keresés végrehajtása mindig kihívást jelent, de nem lehetetlen.
A való életben semmiféle minta nélkül fogunk keresni. Csak azokra a helyekre megyünk, ahol úgy gondoljuk, hogy elhelyezhető. A legtöbb esetben nem követünk semmilyen mintát.
Ugyanez működik a programozási világban?
Nem! kell valami minta a programokban való kereséshez. Ebben a cikkben olyan algoritmusokat fogunk látni, amelyek különböző keresési mintákat követnek.
Számos algoritmus található a programozási világban. Ebben a cikkben a legfontosabb és leggyakrabban használt algoritmusokat tárgyaljuk. Az algoritmusok többi részét pedig el kell tanulnia.
A keresés ebben a cikkben a tömb elemeinek keresését jelenti.
Lássuk őket egyenként.
Tartalomjegyzék
Lineáris keresés
A név azt sugallja, hogy a lineáris keresési algoritmus a lineáris mintát követi a tömb elemeinek kereséséhez. Az algoritmus a tömb elejétől kezdi az elem keresését, és a végére halad, amíg meg nem találja az elemet. Leállítja a program végrehajtását, ha megtalálja a kívánt elemet.
Illusztráljuk a lineáris keresési algoritmusokat néhány remek illusztrációval az algoritmus jobb megértése érdekében.
Ha figyelmesen figyeli a keresési mintát, azt fogja tapasztalni, hogy a program végrehajtásához szükséges idő a legrosszabb esetben O(n) lesz. Figyelembe kell vennünk az elemzendő algoritmusok legrosszabb időbeli összetettségét. Ezért az algoritmus időbonyolultsága O(n).
Lássuk a lineáris keresési algoritmus megvalósítását.
Lineáris keresés megvalósítása
Most már jól ismeri a lineáris keresési algoritmust. Ideje bepiszkítani a kezünket valamilyen kóddal. Nézzük először a lineáris keresés megvalósításának lépéseit. Aztán megpróbálod kódolni. Ne aggódj még akkor sem, ha nem tudsz; Utána megadom a kódot.
Lássuk a lineáris keresési algoritmus megvalósításának lépéseit.
- Inicializálja az elemek tömbjét (a szerencseszámait).
- Írjon egy keresési_elem nevű függvényt, amely három argumentumot fogad el, a tömböt, a tömb hosszát és a keresendő elemet.
- search_element(arr, n, elem):
- Iteráljon a megadott tömbön.
- Ellenőrizze, hogy az aktuális elem megegyezik-e a szükséges elemmel.
- Ha igen, adja vissza a True-t.
- A ciklus befejezése után, ha a végrehajtás még a függvényben van, akkor az elem nincs jelen a tömbben. Ezért adja vissza a False-t.
- Iteráljon a megadott tömbön.
- Nyomtassa ki az üzenetet a search_element függvény visszatérési értéke alapján.
Végül a fenti lépések segítségével írja meg a kódot a lineáris keresési algoritmus megvalósításához.
Befejezte a lineáris keresési algoritmus megvalósítását? Remélem. Ha kitöltötte, akkor ellenőrizze a következő kóddal.
Ha nem fejezte be, ne aggódjon,; tekintse meg az alábbi kódot, és ismerje meg, hogyan valósítottuk meg. Nagy erőfeszítés nélkül megkapod.
## searching function def search_element(arr, n, element): ## iterating through the array for i in range(n): ## checking the current element with required element if arr[i] == element: ## returning True on match return True ## element is not found hence the execution comes here return False if __name__ == '__main__': ## initializing the array, length, and element to be searched arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10 element_to_be_searched = 6 # element_to_be_searched = 11 if search_element(arr, n, element_to_be_searched): print(element_to_be_searched, "is found") else: print(element_to_be_searched, "is not found")
Először futtassa a programot a tömbben található elemmel. Ezután hajtsa végre egy olyan elemmel, amely nem szerepel a tömbben.
A lineáris keresési algoritmus időbonyolultsága O(n).
Csökkenthetjük egy kicsit tovább különböző mintákkal?
Igen, megtehetjük. Lássuk.
Bináris keresés
A bináris keresési algoritmus mindig a tömb középső elemét ellenőrzi. Ez az algoritmus egy rendezett tömbben keresi az elemet.
A bináris keresési algoritmus iterál a tömbön, és ellenőrzi a középső elemet, ha megtalálja, majd leállítja a programot. Ellenkező esetben, ha a középső elem kisebb, mint a kívánt elem, akkor a tömb bal oldali részét a középső elemből kihagyja a keresésből. Ellenkező esetben, ha a középső elem nagyobb, mint a kívánt elem, akkor a tömb jobb oldali részét a középső elemből kihagyja a keresésből.
Minden iterációban a bináris keresési algoritmus levágja az elem kereséséhez szükséges területet. Tehát az ellenőrzések száma kevesebb, mint a lineáris keresési algoritmusban végrehajtott ellenőrzések száma.
Az illusztrációk segítenek a bináris keresési algoritmus jobb megértésében. Vizsgáljuk meg őket.
A bináris keresési algoritmus időbonyolultsága O(log n). Minden iterációban a keresési terület hossza felére csökken. Exponenciálisan csökken.
Bináris keresés megvalósítása
Először látni fogjuk a bináris keresési algoritmus megvalósításának lépéseit, majd a kódot. Lássuk a bináris keresési algoritmus megvalósításának lépéseit.
- A tömb inicializálása elemekkel (a szerencseszámaival)
- Írjon egy keresési_elem nevű függvényt, amely három argumentumot, rendezett tömböt, a tömb hosszát és a keresendő elemet fogadja el.
- search_element(sorted_arr, n, element):
- Inicializálja az i indexváltozót a tömb iterációjához.
- Ezután inicializáljon két változót, hogy fenntartsa a tömb keresési területét. Itt kezdésnek és végnek nevezzük őket, mivel indexeket jelölnek.
- Addig iteráljon, amíg az i kisebb lesz, mint a tömb hossza.
- Számítsa ki a keresési terület középső indexét a kezdő és végértékek felhasználásával. Ez lesz (kezdet + vége) // 2.
- Ellenőrizze, hogy a keresési terület középső indexelt eleme megegyezik-e a kívánt elemmel.
- Ha igen, adja vissza a True-t.
- Ellenkező esetben, ha a középső indexelt elem kisebb, mint a szükséges elem, akkor mozgassa a keresési terület kezdőindexét a középső + 1-re.
- Ellenkező esetben, ha a középső indexelt elem nagyobb, mint a szükséges elem, akkor mozgassa a keresési terület végindexét a középső – 1-re.
- Növelje az i tömb indexét.
- A ciklus befejezése után, ha a végrehajtás még a függvényben van, akkor az elem nincs jelen a tömbben. Ezért adja vissza a False-t.
- Nyomtassa ki az üzenetet a search_element függvény visszatérési értéke alapján.
Próbáld meg a lineáris keresési algoritmus megvalósításához hasonló kódot írni.
…
Megkaptad a kódot?
Igen, hasonlítsa össze az alábbi kóddal. Nem, ne aggódj; megértse a megvalósítást az alábbi kóddal.
## searching function def search_element(sorted_arr, n, element): ## array index for iteration i = 0 ## variables to track the search area ## initializing them with start and end indexes start = 0 end = n - 1 ## iterating over the array while i < n: ## getting the index of the middle element middle = (start + end) // 2 ## checking the middle element with required element if sorted_arr[middle] == element: ## returning True since the element is in the array return True elif sorted_arr[middle] < element: ## moving the start index of the search area to right start = middle + 1 else: ## moving the end index of the search area to left end = middle - 1 i += 1 return False if __name__ == '__main__': ## initializing the array, length, and element to be searched arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10 element_to_be_searched = 9 # element_to_be_searched = 11 if search_element(arr, n, element_to_be_searched): print(element_to_be_searched, "is found") else: print(element_to_be_searched, "is not found")
Tesztelje a kódot különböző esetekben, amikor az elem jelen van, és bizonyos esetekben nincs jelen.
Következtetés
A bináris keresési algoritmus sokkal hatékonyabb, mint a lineáris keresési algoritmus. Rendezni kell a tömböt a bináris keresési algoritmushoz, ez nem így van a lineáris keresési algoritmusban. A válogatás eltart egy ideig. De hatékony algoritmusok rendezése jó kombinációt alkot a bináris keresési algoritmussal.
Most már jól ismeri a Python legszélesebb körben használt algoritmusait.
Ezután ismerkedjen meg néhány népszerű saját üzemeltetésű keresőszoftverrel.
Boldog kódolást 🙂 🧑💻