Lineaarne otsing: Python, C++ Näide

Mis on otsingualgoritm?

Otsingualgoritm on loodud elemendi või objekti leidmiseks antud andmestruktuuriga elementide või objektide kogumist. Näiteks otsige antud kõrguste loendist minimaalset kõrgust või otsige loendist või arvumassiivist kõrgeimat tähist. Vähesed populaarsed otsingualgoritmid hõlmavad "Lineaarne otsing", "Binaarne otsing", "Jump Search", "Fibonacci otsing" jne.

Mis on lineaarne otsing?

Lineaarne otsing on üks lihtsamaid otsingualgoritme. Antud loendist või massiivist otsib see antud elementi ükshaaval. Lineaarne otsing kordab kogu loendit ja kontrollib, kas mõni konkreetne element võrdub 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 massiivist 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, et massiiv, mis sisaldab täisarve. Ülesanne on leida massiivist etteantud 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) Algatage 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 üksus on leitud indeksist nr i). Minge 8. sammu juurde.

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.

Pseudokood järjestikuse otsingu algoritmi jaoks

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++ Koodi näide Lineaarne otsing

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

Väljund:

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

Python Koodi näide Lineaarne otsing

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 aja keerukus protsessori teatud ülesande täitmiseks kuluvat aega. Lineaarses otsingualgoritmis on ülesandeks leida massiivi elemendist otsinguvõti.

Ajalisi keerukusi on kolme tüüpi:

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

Lineaarse otsingu ajaline keerukus halvima stsenaariumi korral:

Oletame, et peame sooritama lineaarse otsingu massiivist, mille suurus on “n”. Otsinguüksuse leiame vahemikus 0 kuni n-1. Halvima stsenaariumi korral proovib algoritm kõiki massiivi elemente otsinguelemendiga sobitada.

Sel juhul on halvimal juhul keerukus O(n). Siin tähendab "O"-suur O-tähistus keerukuse funktsiooni.

Lineaarse otsingu ajaline keerukus parima stsenaariumi korral:

Oletame, et otsime elementi, mis asub massiivi esimesel positsioonil. Selle stsenaariumi korral ei otsi lineaarne otsingualgoritm massiivi kõiki n elementi. Seega on keerukus O(1). See tähendab pidevat 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 ruumiline keerukus

Lineaarse otsingu ruumi keerukus on alati O(N), kuna me ei pea lineaarses otsingufunktsioonis salvestama ega kasutama ühtegi ajutist muutujat.

Lineaarse otsingu algoritmi täiustamine

Otsingut saab programmi elutsükli jooksul teha mitu korda. Samuti on võimalik, et kasutame lineaarset otsingualgoritmi ja otsime mis tahes konkreetset võtit mitu korda. Saame kasutada "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:

Selle meetodi puhul vahetame otsinguelemendi massiivi eelmise elemendiga. Oletame näiteks, et teil on järgmine 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) Vahetage andmed [5] ja andmed[4]. Seejärel näeb andmemassiivi välja selline:

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

Nüüd, kui märkate, et mida sagedamini võtit otsitakse, seda rohkem see indeksit vähendab. Seega väheneb võrdluste arv.

Liikuge ette:

Selle meetodi puhul vahetame otsinguelemendi 0. indeksis. Sest kui seda uuesti otsida, leiame selle O(1) ajal.

Lineaarse otsingu algoritmi rakendamine

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

• Väikeste massiivide või ainult mõne loendi elemendi puhul 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.