Peräkkäishaku

Tietojenkäsittelytieteessä peräkkäishaku eli lineaarihaku on yksinkertainen hakualgoritmi, joka etsii arvoa taulukosta käymällä sen läpi alkio alkiolta. Toisin kuin puolitushaku tai interpolaatiohaku, peräkkäishaku ei vaadi, että alkiot ovat suuruusjärjestyksessä.

Peräkkäishaku yleistyy jokaiselle tietorakenteelle, jonka alkiot voidaan luetella yksi kerrallaan (iteroituva tietorakenne) ja jonka alkioille on määritelty yhtäsuuruus.

Algoritmi

Peräkkäishaun periaate voidaan muotoilla seuraavasti:

Jos taulukon ensimmäinen alkio on etsitty arvo, palautetaan sen indeksi eli 0.
Jos taulukon toinen alkio on etsitty arvo, palautetaan sen indeksi eli 1.
Toistetaan vastaavasti kolmannelle alkiolle, neljännelle alkiolle...
Jos viimeinenkään alkio ei ole etsitty arvo, palautetaan ”ei löytynyt” eli –1.

Seuraava on pseudokoodina toteutettu peräkkäishakualgoritmi, joka kertoo arvon x indeksin taulukossa T:

T: taulukko [0 ... n – 1]
n: taulukon pituus eli alkioiden lukumäärä
x: etsittävä arvo

Palauttaa:
 * indeksin i ensimmäiseen alkioon, joka on yhtä suuri kuin x  (eli jos x = T[i])
 * –1, jos arvoa ei löydy

function peräkkäishaku(T, n, x)
    for i := 0 to n – 1 do
        if T[i] = x then
            return i
        end if
    end for
    return –1
end function

Suorituskyky

Peräkkäishaun asymptoottinen suoritusaika on kertaluokkaa O(n). Jos oletetaan että haettava alkio esiintyy taulukossa, niin sen etsimiseen satunnaisesti järjestetystä n:n pituisesta taulukosta tarvitaan keskimäärin n / 2 vertailua. Parhaimmassa tapauksessa, jossa etsitty alkio on taulukon ensimmäinen alkio, tarvitaan yksi vertailu. Pahimmassa tapauksessa, jolloin etsitty alkio ei esiinny taulukossa lainkaan, algoritmi tekee syötteen pituuden verran eli n kappaletta vertailuja.

Samat luvut pätevät jokaiselle tietorakenteelle, jossa seuraavaan alkioon siirtyminen vie aina saman verran aikaa.

Erityissovelluksia

Peräkkäishaku yhdistettynä tietuealkioihin mahdollistaa ajassa O(n) toimivan hakurakenteen eli assosiaatiotaulun toteuttamisen lähes minkä tietorakenteen avulla tahansa. Esimerkkitoteutus taulukkona:

record Alkio
    key: avain, jonka perusteella arvoja noudetaan ja jolle on määritelty yhtäsuuruus
    value: arvo, varsinainen tietoalkio
end record

T: taulukko, jonka alkiot ovat tyyppiä Alkio
n: taulukon pituus
k: haettava avain

function lookup(T, n, k)
    for i := 0 to n – 1 do
        if T[i].key = k then
            return T[i].value
        end if
    end for
    return ei löytynyt
end function

Tehokkaampia hakurakennetoteutuksia ovat hajautustaulu ja tasapainoinen hakupuu.

Katso myös

Hakualgoritmeja