Lineáris keresés: Python, C++ Példa
Sarah Chen
Mi az a keresési algoritmus?
A keresőalgoritmus arra szolgál, hogy egy adott adatszerkezettel rendelkező elemek vagy objektumok gyűjteményéből egy elemet vagy objektumot találjon meg. Például keresse meg a minimális magasságot egy adott magasságlistából, vagy keresse meg a legmagasabb jelölést egy listából vagy számtömbből. Néhány népszerű keresési algoritmus közé tartozik a „Lineáris keresés”, „Bináris keresés”, „Jump Search”, „Fibonacci Search” stb.
Mi az a lineáris keresés?
A lineáris keresés az egyik legegyszerűbb keresési algoritmus. Adott listából vagy tömbből egyenként megkeresi az adott elemet. A Lineáris keresés a teljes listán iterál, és ellenőrzi, hogy egy adott elem megegyezik-e a keresési elemmel. Úgy is hívják szekvenciális keresés.
Mit csinál a Lineáris kereső funkció?
Az egész számok tömbje a következőképpen van megadva: "Numbers”, és egy „elem” változó tartalmazza a keresendő egész számot.
Most a Lineáris keresési algoritmus a következő kimenetet tudja biztosítani:
- „-1”; ez azt jelenti, hogy az adott elem nem található a tömbben
- Bármely szám 0 és n-1 között; azt jelenti, hogy a keresési elem megtalálható, és visszaadja az elem indexét a tömbön. Itt az „n” a tömb méretét jelenti.
Hogyan működik a Lineáris keresés?
Tegyük fel, hogy egy egész számokat tartalmazó tömb. A feladat egy adott szám megtalálása a tömbben.
- Ha a szám a tömbben található, akkor az adott szám indexét kell visszaadnunk.
- Ha a megadott szám nem található, akkor -1-et ad vissza.
A folyamatábrán a „Data” az egész tömb, az „N” a tömb mérete, az „elem” pedig az a szám, amelyet a tömbben keresni szeretnénk.
Folyamatábra a lineáris keresési algoritmushoz:
Íme a folyamatábra lépései:
Step 1) Olvassa el a keresett elemet: „tétel”.
Step 2) Kezdeményezzük i=0 és index=-1
Step 3) Ha én
Step 4) Ha az Adat[i] egyenlő a „tétellel”, akkor folytassa az 5. lépéssel. Ellenkező esetben folytassa a 6. lépéssel.
Step 5) Index = i (Mivel az elem az i indexnél található). Folytassa a 8. lépéssel.
Step 6) i = i +1.
Step 7) Folytassák a 3. lépéssel.
Step 8) Leállítása.
Az egyszerűség kedvéért adunk egy példát egész számok tömbjével. A lineáris keresés a karakterláncban, objektumok tömbjében vagy struktúrában is alkalmazható.
Pszeudo kód a szekvenciális keresési algoritmushoz
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ Kódpélda Lineáris keresés
#include < bits / stdc++.h >
using namespace std;
int linearSearch(int * arr, int item, int n) {
int idx = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == item) {
idx = i;
break;
}
}
return idx;
}
int main() {
int array[] = {
1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
};
int n = sizeof(array) / sizeof(arr[0]);
int item;
cout << "Enter a number to search: ";
cin >> item;
int idx = linearSearch(arr, item, n);
if (idx >= 0) {
cout << item << " is found at index " << idx << endl;
} else {
cout << "Could not find " << item << " in the array" << endl;
}
}
output:
Enter a number to search: -10 -10 is found at index 14
Python Kódpélda Lineáris keresés
def linearSearch(data, item):
for i in range(len(data)):
if data[i] == item:
return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
print("{} is found at index {}".format(item, idx))
else :
print("{} was not found".format(item))
output:
Enter a number to search: -10 -10 is found at index 14
Lineáris keresési algoritmus komplexitáselemzése
Az időbonyolultság általában azt jelenti, hogy a CPU mennyi időt fordít egy bizonyos feladat elvégzésére. A lineáris keresési algoritmusban az a feladat, hogy a tömb eleméből megkeressük a keresőkulcsot.
Az időbonyolítás három típusa:
- A legrosszabb esetben
- Legjobb forgatókönyv
- Átlagos eset forgatókönyv
A lineáris keresés időbeli összetettsége a legrosszabb forgatókönyvben:
Tegyük fel, hogy lineáris keresést kell végrehajtanunk egy „n” méretű tömbben. A keresett elemet 0 és n-1 index között találjuk. A legrosszabb forgatókönyv esetén az algoritmus megpróbálja a tömb összes elemét a keresési elemmel egyeztetni.
Ebben az esetben a legrosszabb eset bonyolultsága O(n). Itt az „O”-nagy O-jelölés a komplexitási függvényt jelenti.
A lineáris keresés időbeli összetettsége a legjobb forgatókönyvben:
Tegyük fel, hogy egy olyan elemet keresünk, amely a tömb első pozíciójában található. Ebben a forgatókönyvben a lineáris keresési algoritmus nem keresi meg a tömb összes n elemét. Tehát a komplexitás O(1) lesz. Ez állandó időt jelent.
A lineáris keresés időbonyolultsága átlagos esetben:
Ha egy elemet találunk a tömb középső indexénél, akkor elmondható, hogy a lineáris keresés átlagos esetkomplexitása O(N), ahol N a tömb hosszát jelenti.
A lineáris keresési algoritmus térkomplexitása
A lineáris keresés térbonyolultsága mindig O(N), mert nincs szükségünk semmilyen ideiglenes változó tárolására vagy használatára a lineáris keresési függvényben.
A lineáris keresési algoritmus javítása
A keresés a program életciklusa során többször is elvégezhető. Az is lehetséges, hogy a lineáris keresési algoritmust futtatjuk, és többször keresünk egy adott kulcsot. Használhatjuk a „Bináris keresési algoritmus” ha a tömb rendezett tömb.
Tegyük fel, hogy a tömb 10 ezer számból áll, és a célelem az 5000. indexnél található. Tehát az algoritmus 5000 elemet próbál meg összehasonlítani. Most az összehasonlítás CPU-igényes feladatok. A lineáris keresési algoritmus optimalizálására két lehetőségünk van.
- Átültetés
- Lépjen az elülső oldalra
Átültetés:
Ennél a módszernél a keresési elemet felcseréljük a tömb előző elemével. Tegyük fel például, hogy van egy ilyen tömbje:
Adat[] = {1,5,9,8,7,3,4,11}
Most keresni akarunk 4. Az átültetés lépései:
Step 1) A „4” a 6-os indexnél található. Hat összehasonlításra volt szükség.
Step 2) Adatok[6] és adatok[5] felcserélése. Ezután az adattömb így fog kinézni:
Adat[] = {1,5,9,8,7,4,3,11}
Step 3) Keresse meg újra a 4-et. Az 5. indexnél található. Ezúttal öt összehasonlítás kellett.
Step 4) Adatok felcserélése [5] és adat[4]. Ekkor az adattömb így fog kinézni:
Adatok [] = {1,5,9,8,4,7,3,11}
Most, ha észreveszi, minél gyakrabban keres egy kulcsot, annál jobban csökkenti az indexet. Így csökken az összehasonlítások száma.
Menj előre:
Ennél a módszernél felcseréljük a keresőelemet a 0. indexben. Mert ha újra rákeresünk, akkor O(1) időpontban megtaláljuk.
Lineáris keresési algoritmus alkalmazása
Íme néhány lineáris keresőalkalmazás, amelyet használhatunk.
- Kis méretű tömbök vagy csak néhány elem esetén egyszerűbb a lineáris keresés használata.
- Lineáris keresési módszer használható egyetlen ill többdimenziós tömbök vagy más adatszerkezetek.
- Általában a lineáris keresés egyszerű és hatékony a „rendezetlen” adatokban történő keresés végrehajtásához. A megadott rendezetlen listából egyszerűen lekérhetünk egyetlen adatot.
