Lineáris keresés: Python, C++ Példa

Mi az a keresési algoritmus?

Egy keresőalgoritmus célja, hogy egy adott adatszerkezetű elem- vagy objektumhalmazból egy elemet vagy objektumot találjon. Például egy adott magasságlistából megkeresheti a minimális magasságot, vagy egy számlistából vagy tömbből a legmagasabb értéket. Néhány népszerű keresőalgoritmus a „lineáris keresés”, a „bináris keresés”, az „ugró keresés”, a „Fibonacci-keresés” stb.

Mi az a lineáris keresés?

Lineáris keresés az egyik legegyszerűbb keresési algoritmus. Egy adott listából vagy tömbből egyesével keresi meg az adott elemet. A lineáris keresés végigmegy a teljes listán, és ellenőrzi, hogy bármelyik elem egyenlő-e a keresett elemmel. Más néven 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 a megadott 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öt kell megtalálnunk a tömbben. A feladat az, hogy egy adott számot találjunk.

• 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) Iniciáld az i=0 és az index=-1 értékeket.

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. indexszám alatt 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 Code szekvenciális keresési algoritmushoz

A következő pszeudokód a fent leírt lineáris keresés logikáját ragadja meg. Az első indextől kezdve végigjárja a tömböt, és egyezés esetén visszaadja a pozíciót, egyébként -1-et ad vissza.

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 a negative index is not valid
    return -1

C++ Code Példa Lineáris keresésre

Itt egy teljes C++ Egy program, amely szekvenciális keresést valósít meg és kinyomtatja a keresett érték indexét.

#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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Példa Lineáris keresésre

Ugyanez a logika a Python egyetlen ciklust használ a listaindexek felett, és visszaadja a talált elem pozícióját.

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 mennyi CPU-időre van szükség egy adott feladat végrehajtásához. A lineáris keresési algoritmusban a feladat a keresési kulcs megtalálása a tömb elemei közül.

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 meg. A legrosszabb esetben az algoritmus megpróbálja a tömb összes elemét a keresett elemmel párosítani.

Ebben az esetben a legrosszabb esetben a komplexitás O(n) lesz. Itt az „O” – nagy O jelölés – a komplexitásfü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 az esetben a lineáris keresési algoritmus nem fogja megtalálni mind az n elemet a tömbben. Tehát a komplexitás O(1) lesz. Ez konstans 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érbeli komplexitása:

A lineáris keresés térbeli komplexitása mindig O(N), mivel a lineáris keresési függvényben nem kell semmilyen ideiglenes változót tárolnunk vagy használnunk.

A lineáris keresési algoritmus javítása

A keresés többször is elvégezhető a program életciklusa során. Az is lehetséges, hogy a lineáris keresési algoritmust futtatjuk, és egy adott kulcsot többször is keresünk. 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:

Ebben a metódusban a keresési elemet felcseréljük a tömbben az előző elemével. Tegyük fel például, hogy van egy ilyen tömbünk:

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) Cserélje fel a data[5] és data[4] elemeket. Ekkor az adattömb így fog kinézni:

Adat[] = {1,5,9,8,4,7,3,11}

Most, ha megfigyeled, minél gyakrabban keresünk egy kulcsot, annál jobban csökkenti az indexet. Így csökken az összehasonlítások száma is.

Menj előre:

Ebben a metódusban a keresési elemet a 0. indexűre cseréljük. Mert ha újra keressük, akkor O(1) időpontban megtalálhatjuk.

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 a lista csak néhány eleme esetén egyszerűbb a lineáris keresést használni.
• 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.

GYIK