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 

 Puolitushaku
 Interpolaatiohaku

Peräkkäishakuun soveltuvia tietorakenteita 

 Taulukko
 Linkitetty lista

Tehokkaampia hakuja mahdollistavia rakenteita 

 Hakupuu
 Punamusta puu
 Hajautustaulu

Algoritmit