Lineaarinen haku: Python, C++ esimerkki

Mikä on hakualgoritmi?

Hakualgoritmi on suunniteltu etsimään elementti tai objekti kokoelmasta elementtejä tai objekteja, joilla on tietty tietorakenne. Voit esimerkiksi etsiä vähimmäiskorkeutta tietystä korkeusluettelosta tai etsiä korkeinta arvoa luettelosta tai lukujoukosta. Muutamia suosittuja hakualgoritmeja ovat "Lineaarinen haku", "Binaarihaku", "Jump Search", "Fibonacci Search" jne.

Mikä on lineaarinen haku?

Lineaarinen haku on yksi yksinkertaisimmista hakualgoritmeista. Tietystä luettelosta tai taulukosta se etsii tiettyä elementtiä yksitellen. Lineaarinen haku toistuu koko luettelossa ja tarkistaa, vastaako jokin tietty elementti hakuelementin kanssa. Sitä kutsutaan myös peräkkäinen haku.

Mitä lineaarinen hakutoiminto tekee?

Kokonaislukujen joukko annetaan muodossa "Numbers”, ja muuttuja ”item” sisältää haettavan kokonaisluvun.

Lineaarinen hakualgoritmi voi nyt tarjota seuraavan tuloksen:

• "-1"; tämä tarkoittaa, että annettua elementtiä ei löydy taulukosta
• Mikä tahansa luku väliltä 0 - n-1; tarkoittaa, että hakuelementti löytyy, ja se palauttaa taulukossa olevan elementin indeksin. Tässä "n" edustaa taulukon kokoa.

Kuinka lineaarinen haku toimii?

Oletetaan taulukko, joka sisältää kokonaislukuja. Tehtävänä on löytää taulukosta tietty numero.

• Jos numero sijaitsee taulukossa, meidän on palautettava kyseisen luvun indeksi.
• Jos annettua numeroa ei löydy, se palauttaa -1.

Vuokaaviossa "Data" on kokonaislukutaulukko, "N" on taulukon koko ja "tuote" on numero, jonka haluamme etsiä taulukosta.

Lineaarisen hakualgoritmin vuokaavio:

Tässä ovat vuokaavion vaiheet:

Vaihe 1) Lue hakukohde "tuote".

Vaihe 2) Aloita i=0 ja index=-1

Vaihe 3) Jos minä

Vaihe 4) Jos Data[i] on yhtä kuin "tuote", siirry vaiheeseen 5. Muussa tapauksessa siirry vaiheeseen 6.

Vaihe 5) Indeksi = i (Koska kohde löytyy indeksistä nro i). Siirry vaiheeseen 8.

Vaihe 6) i = i +1.

Vaihe 7) Siirry vaiheeseen 3.

Vaihe 8) Lopeta.

Yksinkertaisuuden vuoksi tarjoamme esimerkin, jossa on joukko kokonaislukuja. Lineaarihakua voidaan käyttää myös merkkijonossa, objektijoukossa tai rakenteessa.

Pseudokoodi peräkkäiselle hakualgoritmille

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++ Koodiesimerkki Lineaarinen haku

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

lähtö:

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

Python Koodiesimerkki Lineaarinen haku

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

lähtö:

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

Lineaarisen hakualgoritmin monimutkaisuusanalyysi

Yleisesti aikamonimutkaisuus tarkoittaa sitä, kuinka paljon suorittimen aikaa tietyn tehtävän suorittamiseen kuluu. Lineaarisessa hakualgoritmissa tehtävänä on löytää hakuavain taulukon elementistä.

Kolmen tyyppisiä aikakomplikaatioita ovat:

• Pahimmassa tapauksessa
• Paras tapaus
• Keskimääräinen tapausskenaario

Lineaarisen haun aika monimutkaisuus pahimmassa mahdollisessa skenaariossa:

Oletetaan, että meidän on suoritettava lineaarinen haku taulukossa, jonka koko on “n”. Löydämme hakukohteen indeksien 0 ja n-1 välillä. Pahimmassa tapauksessa algoritmi yrittää sovittaa kaikki taulukon elementit hakuelementtiin.

Siinä tapauksessa pahimman tapauksen monimutkaisuus on O(n). Tässä "O"-iso O-merkintä tarkoittaa monimutkaisuusfunktiota.

Lineaarisen haun aika monimutkaisuus parhaassa tapauksessa:

Oletetaan, että etsimme elementtiä, joka sijaitsee taulukon ensimmäisessä paikassa. Tässä skenaariossa lineaarinen hakualgoritmi ei etsi kaikkia taulukon n elementtiä. Joten monimutkaisuus on O(1). Tämä tarkoittaa jatkuvaa aikaa.

Aika Lineaarisen haun monimutkaisuus keskimääräisessä tapauksessa:

Kun elementti löytyy taulukon keskiindeksistä, voidaan sanoa, että keskimääräinen tapausten kompleksisuus lineaarihaussa on O(N), missä N tarkoittaa taulukon pituutta.

Lineaarisen hakualgoritmin avaruuden monimutkaisuus

Lineaarihaun avaruuden monimutkaisuus on aina O(N), koska meidän ei tarvitse tallentaa tai käyttää mitään väliaikaista muuttujaa lineaarihakufunktiossa.

Lineaarisen hakualgoritmin parantaminen

Haku voidaan tehdä useita kertoja ohjelman elinkaaren aikana. On myös mahdollista, että käytämme lineaarista hakualgoritmia ja etsimme mitä tahansa tiettyä avainta useita kertoja. Voimme käyttää "Binäärihakualgoritmi", jos taulukko on lajiteltu matriisi.

Oletetaan, että taulukko koostuu 10 tuhannesta numerosta ja kohdeelementti löytyy 5000. indeksistä. Joten algoritmi yrittää vertailla 5000 elementtiä. Nyt vertailut ovat prosessoriraskaita tehtäviä. Lineaarisen hakualgoritmin optimoimiseksi meillä on kaksi vaihtoehtoa.

• saattaminen osaksi
• Siirrä Eteen

Transponointi:

Tässä menetelmässä vaihdamme hakuelementin sen edellisen elementin kanssa taulukossa. Oletetaan esimerkiksi, että sinulla on seuraavanlainen taulukko:

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

Nyt haluamme etsiä 4. Transponoinnin vaiheet:

Vaihe 1) "4" löytyy indeksistä 6. Vertailua tarvittiin kuusi.

Vaihe 2) Vaihda tiedot[6] ja tiedot[5]. Sitten datataulukko näyttää tältä:

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

Vaihe 3) Etsi 4 uudelleen. Löytyy indeksistä 5. Tällä kertaa vertailua tarvittiin viisi.

Vaihe 4) Vaihda tiedot [5] ja tiedot[4]. Sitten datataulukko näyttää tältä:

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

Jos nyt huomaat, mitä useammin avainta etsitään, sitä enemmän se pienentää indeksiä. Näin ollen vertailujen määrä vähenee.

Siirry eteen:

Tässä menetelmässä vaihdamme hakuelementin 0. indeksissä. Koska jos sitä etsitään uudelleen, voimme löytää sen O(1) aikaan.

Lineaarisen hakualgoritmin soveltaminen

Tässä on joitain lineaarisia hakusovelluksia, joita voimme käyttää.

• Pienikokoisille taulukoille tai vain muutamalle listan elementille on helpompi käyttää lineaarihakua.
• Lineaarista hakumenetelmää voidaan käyttää yksittäisessä tai moniulotteisia taulukoita tai muita tietorakenteita.
• Yleensä lineaarinen haku on yksinkertainen ja tehokas haun suorittamiseen "järjestämättömästä" tiedosta. Voimme hakea yksittäisen tiedon annetusta järjestämättömästä luettelosta helposti.