Binaarihaku vs lineaarinen haku
Lineaarinen haku, joka tunnetaan myös nimellä peräkkäinen haku, on yksinkertaisin hakualgoritmi. Se etsii luettelosta tiettyä arvoa tarkistamalla jokaisen luettelon elementin. Binaarihaku on myös menetelmä, jota käytetään määritetyn arvon paikantamiseen järjestetyssä luettelossa. Binäärihakumenetelmä puolittaa tarkistettujen elementtien määrän (jossakin iteraatiossa), mikä vähentää aikaa, joka kuluu tietyn kohteen paikantamiseen luettelosta.
Mikä on lineaarinen haku?
Lineaarinen haku on yksinkertaisin hakumenetelmä, joka tarkistaa luettelon jokaisen elementin peräkkäin, kunnes se löytää tietyn elementin. Lineaarisen hakumenetelmän syöte on sekvenssi (kuten taulukko, kokoelma tai merkkijono) ja etsittävä alkio. Tulos on tosi, jos määritetty kohde on annetussa järjestyksessä, tai epätosi, jos se ei ole järjestyksessä. Koska tämä menetelmä tarkistaa luettelon jokaisen kohteen, kunnes määritetty kohde löytyy, se käy pahimmassa tapauksessa läpi kaikki luettelon elementit ennen kuin se löytää vaaditun elementin. Lineaarihaun monimutkaisuus on o(n). Siksi sen katsotaan olevan liian hidas käytettäväksi haettaessa elementtejä suurista luetteloista. Mutta tämä on hyvin yksinkertainen ja helpompi toteuttaa.
Mikä on binäärihaku?
Binaarihaku on myös menetelmä, jota käytetään tietyn kohteen paikantamiseen järjestetyssä luettelossa. Tämä menetelmä alkaa vertaamalla haettua elementtiä luettelon keskellä oleviin elementteihin. Jos vertailu määrittää, että kaksi elementtiä ovat yhtä suuret, menetelmä pysähtyy ja palauttaa elementin sijainnin. Jos etsitty elementti on suurempi kuin keskimmäinen elementti, se aloittaa menetelmän uudelleen käyttämällä vain lajitellun luettelon alaosaa. Jos etsittävä elementti on pienempi kuin keskimmäinen elementti, se aloittaa menetelmän uudelleen käyttämällä vain lajitellun luettelon yläosaa. Jos etsitty elementti ei ole luettelossa, menetelmä palauttaa yksilöllisen arvon, joka osoittaa sen. Siksi binäärihakumenetelmä puolittaa vertailtavien elementtien määrän (jossakin iteraatiossa) vertailun tuloksesta riippuen. Näin ollen binäärihaku suoritetaan logaritmisessa ajassa, mikä johtaa o(log n) tapausten keskimääräiseen suorituskykyyn.
Mitä eroa on binäärihaun ja lineaarihaun välillä?
Vaikka sekä lineaarinen että binäärihaku ovat hakumenetelmiä, niillä on useita eroja. Vaikka binäärihaku toimii lajiteltujen listojen perusteella, linjahaku voi toimia myös lajittelemattomissa listoissa. Listan lajittelun tapausten keskimääräinen monimutkaisuus on yleensä n log n. lineaarinen haku on yksinkertainen ja selkeä toteuttaa kuin binäärihaku. Mutta lineaarinen haku on liian hidas käytettäväksi suurilla listoilla sen o(n) keskimääräisen tapauksen suorituskyvyn vuoksi. Toisa alta binäärihakua pidetään tehokkaampana menetelmänä, jota voitaisiin käyttää suurilla listoilla. Mutta binäärihaun toteuttaminen voi olla melko hankalaa, ja tutkimus on osoittanut, että tarkka koodi binäärihakuun löytyi vain viidestä kirjasta kahdestakymmenestä.
