Lineaarne otsing: Python, C++ Näide

Mis on otsingualgoritm?

Otsimisalgoritm on loodud elemendi või objekti leidmiseks elementide või objektide kogumist antud andmestruktuuriga. Näiteks otsige antud kõrguste loendist minimaalset kõrgust või otsige numbrite loendist või massiivist kõrgeimat hinda. Mõned populaarsed otsingualgoritmid on näiteks „lineaarne otsing“, „binaarne otsing“, „hüppeotsing“, „Fibonacci otsing“ jne.

Mis on lineaarne otsing?

Lineaarne otsing on üks lihtsamaid otsingualgoritme. Antud loendist või massiivist otsitakse antud elementi ükshaaval. Lineaarne otsing itereerib kogu loendi ulatuses ja kontrollib, kas mõni konkreetne element on võrdne otsinguelemendiga. Seda nimetatakse ka järjestikune otsing.

Mida teeb lineaarse otsingu funktsioon?

Täisarvude massiiv on antud kui "Numbers,” ja muutuja „item” sisaldab otsitavat täisarvu.

Nüüd võib lineaarse otsingu algoritm pakkuda järgmist väljundit:

• „-1”; see tähendab, et antud elementi massiivis ei leidu.
• mis tahes arv vahemikus 0 kuni n-1; tähendab, et otsinguelement on leitud ja tagastab massiivi elemendi indeksi. Siin tähistab "n" massiivi suurust.

Kuidas lineaarne otsing töötab?

Oletame täisarvudest koosnevat massiivi. Ülesanne on leida massiivist antud arv.

• Kui number asub massiivis, peame tagastama selle numbri indeksi.
• Kui antud numbrit ei leita, tagastab see -1.

Vooskeemis on "Data" täisarvude massiiv, "N" on massiivi suurus ja "üks" on number, mida tahame massiivist otsida.

Lineaarse otsingu algoritmi vooskeem:

Siin on vooskeemi sammud:

Step 1) Lugege otsinguüksust "üksus".

Step 2) Initsialiseeri i=0 ja indeks=-1.

Step 3) Kui i

Step 4) Kui Andmed[i] võrdub „üksusega”, minge 5. sammu juurde. Muul juhul jätkake 6. sammuga.

Step 5) Indeks = i (kuna objekt asub indeksil i). Jätka 8. sammuga.

Step 6) i = i +1.

Step 7) Minge 3. sammu.

Step 8) Peatu.

Lihtsuse huvides toome näite täisarvude massiiviga. Lineaarne otsing on rakendatav ka stringi, objektide massiivi või struktuuri puhul.

Pseudo Code järjestikuse otsingu algoritmi jaoks

Järgnev pseudokood tabab ülalkirjeldatud lineaarse otsingu loogikat. See käib läbi massiivi esimesest indeksist ja tagastab positsiooni vaste leidmisel, vastasel juhul tagastab -1.

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 Lineaarse otsingu näide

Siin on täielik C++ Programm, mis rakendab järjestikust otsingut ja prindib otsitava väärtuse indeksi.

#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;
    }
}

Väljund:

Enter a number to search: -10
-10 is found at index 14

Python Code Lineaarse otsingu näide

Sama loogika ka Python kasutab loendiindeksite üle ühte tsüklit ja tagastab sobiva elemendi positsiooni.

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))

Väljund:

Enter a number to search: -10
-10 is found at index 14

Lineaarse otsingu algoritmi keerukuse analüüs

Üldiselt tähendab ajaline keerukus protsessori aega, mis kulub teatud ülesande täitmiseks. Lineaarse otsingu algoritmi puhul on ülesandeks leida otsinguvõti massiivi elementide hulgast.

Ajalisi keerukusi on kolme tüüpi:

• Kõige hullemal juhul
• Parim stsenaarium
• Keskmine juhtumistsenaarium

Lineaarse otsingu ajaline keerukus halvima stsenaariumi korral:

Oletame, et peame teostama lineaarotsingu massiivis suurusega "n". Leiame otsitava elemendi indeksi 0 ja n-1 vahel. Halvimal juhul püüab algoritm leida otsinguelemendile vastet kõigile massiivi elementidele.

Sellisel juhul on halvimal juhul keerukus O(n). Siin tähendab „O” – suur O tähistus – keerukusfunktsiooni.

Lineaarse otsingu ajaline keerukus parima stsenaariumi korral:

Oletame, et otsime elementi, mis asub massiivi esimesel positsioonil. Sellisel juhul ei otsi lineaarse otsingu algoritm kõiki massiivi n elementi. Seega on keerukus O(1). See tähendab konstantset aega.

Lineaarse otsingu aja keerukus keskmise stsenaariumi korral:

Kui element on leitud massiivi keskmisest indeksist, siis võib öelda, et lineaarse otsingu puhul on keskmine juhtude keerukus O(N), kus N tähendab massiivi pikkust.

Lineaarse otsingu algoritmi ruumi keerukus:

Lineaarse otsingu ruumi keerukus on alati O(N), sest lineaarse otsingu funktsioonis ei ole vaja salvestada ega kasutada mingeid ajutisi muutujaid.

Lineaarse otsingu algoritmi täiustamine

Otsingut saab programmi elutsükli jooksul teha mitu korda. Samuti on võimalik, et käivitame lineaarse otsingu algoritmi ja otsime mis tahes konkreetset võtit mitu korda. Saame kasutada funktsiooni „Binaarne otsingu algoritm”, kui massiiv on sorteeritud massiiv.

Oletame, et massiiv koosneb 10 tuhandest numbrist ja sihtelement on 5000. indeksis. Seega proovib algoritm võrrelda 5000 elementi. Võrdlused on protsessorit koormavad ülesanded. Lineaarse otsingu algoritmi optimeerimiseks on meil kaks võimalust.

• Ülevõtmine
• Liikuge esiküljele

Ülevõtmine:

Selles meetodis vahetame otsinguelemendi massiivi eelmise elemendiga. Näiteks oletame, et teil on selline massiiv:

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

Nüüd tahame otsida 4. Ülevõtmise sammud:

Step 1) “4” on indeksi 6 juures. Võrdlusi kulus kuus.

Step 2) Andmete[6] ja andmete[5] vahetamine. Seejärel näeb andmemassiivi välja selline:

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

Step 3) Otsige uuesti 4. Leitud indeksilt 5. Seekord kulus viis võrdlust.

Step 4) Vaheta andmed data[5] ja data[4]. Seejärel näeb andmemassiiv välja selline:

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

Nagu te nüüd märganud, mida sagedamini võtit otsitakse, seda rohkem see indeksit vähendab. Seega väheneb võrdluste arv.

Liikuge ette:

Selles meetodis vahetame otsinguelemendi 0. indeksiga. Sest kui seda uuesti otsida, leiame selle ajahetkel O(1).

Lineaarse otsingu algoritmi rakendamine

Siin on mõned lineaarse otsingu rakendused, mida saame kasutada.

• Väikeste massiivide või ainult mõne elemendi puhul loendis on lihtsam kasutada lineaarset otsingut.
• Lineaarset otsingumeetodit saab kasutada üksik- või mitmemõõtmelised massiivid või muud andmestruktuurid.
• Üldiselt on lineaarne otsing lihtne ja tõhus, et sooritada otsingut „järjestamata“ andmetes. Antud järjestamata loendist saame hõlpsalt tuua üksikuid andmeid.

KKK