Lineaarinen haku: Python, C++ esimerkki

Mikä on hakualgoritmi?

Hakualgoritmi on suunniteltu löytämään elementti tai objekti joukosta elementtejä tai objekteja, joilla on tietty tietorakenne. Voit esimerkiksi etsiä pienimmän korkeuden tietystä korkeusluettelosta tai suurimman arvon numeroluettelosta tai -taulukosta. Muutamia suosittuja hakualgoritmeja ovat "lineaarinen haku", "binäärinen haku", "hyppyhaku", "Fibonaccin haku" jne.

Mikä on lineaarinen haku?

Lineaarinen haku on yksi yksinkertaisimmista hakualgoritmeista. Se etsii annetusta listasta tai taulukosta annettua alkiota yksi kerrallaan. Lineaarinen haku iteroi koko listan läpi ja tarkistaa, onko jokin tietty alkio yhtä suuri kuin etsittävä alkio. 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, että taulukko sisältää kokonaislukuja. Tehtävänä on löytää annettu luku taulukosta.

• 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 indeksi=-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.

Pseudo Code peräkkäiselle hakualgoritmille

Seuraava pseudokoodi kuvaa edellä kuvatun lineaarisen haun logiikan. Se käy läpi taulukon ensimmäisestä indeksistä alkaen ja palauttaa osuman sijainnin, muuten se palauttaa arvon -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 Esimerkki lineaarisesta hausta

Tässä on täydellinen C++ ohjelma, joka toteuttaa peräkkäisen haun ja tulostaa haetun arvon indeksin.

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

lähtö:

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

Python Code Esimerkki lineaarisesta hausta

Sama logiikka myös Python käyttää yhtä silmukkaa listaindeksien yli ja palauttaa vastaavan elementin sijainnin.

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 ottaen aikavaativuus tarkoittaa suorittimen käyttämää aikaa tietyn tehtävän suorittamiseen. Lineaarisessa hakualgoritmissa tehtävänä on löytää hakuavain taulukon alkioista.

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". Voimme löytää haettavan alkion indeksien 0 ja n-1 väliltä. Pahimmassa tapauksessa algoritmi yrittää yhdistää kaikki taulukon alkiot haettavaan alkioon.

Siinä tapauksessa pahimman tapauksen kompleksisuus on O(n). Tässä ”O” – big O -merkintä – tarkoittaa kompleksisuusfunktiota.

Lineaarisen haun aika monimutkaisuus parhaassa tapauksessa:

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

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 avaruuskompleksisuus:

Lineaarisen haun avaruusvaativuus on aina O(N), koska lineaarisessa hakufunktiossa ei tarvitse tallentaa tai käyttää minkäänlaisia ​​väliaikaisia ​​muuttujia.

Lineaarisen hakualgoritmin parantaminen

Haku voidaan tehdä useita kertoja ohjelman elinkaaren aikana. On myös mahdollista, että suoritamme lineaarisen hakualgoritmin 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ä metodissa 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 data[5] ja data[4]. Tällöin datataulukko näyttää tältä:

Data[] = {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ä metodissa vaihdamme hakualkion indeksiin 0. Koska jos sitä haetaan uudelleen, löydämme sen ajassa O(1).

Lineaarisen hakualgoritmin soveltaminen

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

• Pienille taulukoille tai vain muutamille alkioille listassa on helpompi käyttää lineaarista hakua.
• 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.

UKK