Binaarihaku vs. lineaarinen haku
Lineaarinen haku, joka tunnetaan myös nimellä peräkkäinen haku, on yksinkertaisin hakualgoritmi. Se etsii määritettyä arvoa luettelosta tarkistamalla kaikki luettelon elementit. Binaarihaku on myös menetelmä, jolla määritetty arvo voidaan etsiä lajitellusta luettelosta. Binaarihakutapa puolittaa tarkastettujen elementtien lukumäärän (kussakin iteraatiossa), mikä lyhentää aikaa, joka kuluu kyseisen kohteen löytämiseen luettelosta.
Mikä on lineaarinen haku?
Lineaarinen haku on yksinkertaisin hakumenetelmä, joka tarkistaa luettelon jokaisen elementin peräkkäin, kunnes se löytää määritetyn elementin. Lineaarisen hakumenetelmän syöttö on sekvenssi (kuten taulukko, kokoelma tai merkkijono) ja kohde, jota on haettava. Lähtö on tosi, jos määritetty kohde on annetussa sekvenssissä, tai epätosi, jos se ei ole järjestyksessä. Koska tämä menetelmä tarkistaa luettelon jokaisen kohteen, kunnes määritetty kohde löytyy, pahimmassa tapauksessa se käy läpi kaikki luettelon elementit ennen kuin löytää tarvittavan elementin. Lineaarisen haun monimutkaisuus on o (n). Siksi sen katsotaan olevan liian hidas käytettäväksi elementtien etsimisessä suurista luetteloista. Mutta tämä on hyvin yksinkertainen ja helpompi toteuttaa.
Mikä on binaarihaku?
Binaarihaku on myös menetelmä, jolla määritetty kohde voidaan etsiä lajitellusta luettelosta. Tämä menetelmä aloitetaan vertaamalla haettua elementtiä luettelon keskellä oleviin elementteihin. Jos vertailussa todetaan, että nämä kaksi elementtiä ovat samat, menetelmä pysähtyy ja palauttaa elementin sijainnin. Jos haettu elementti on suurempi kuin keskielementti, se käynnistää menetelmän uudelleen käyttämällä vain lajiteltujen luetteloiden alaosaa. Jos haettu elementti on pienempi kuin keskielementti, se käynnistää menetelmän uudelleen käyttämällä vain lajiteltujen luetteloiden yläosaa. Jos haettu elementti ei ole luettelossa, menetelmä palauttaa yksilöllisen arvon, joka osoittaa sen. Siksi binaarinen hakumenetelmä puolittaa verrattujen elementtien lukumäärän (kussakin iteraatiossa) riippuen vertailun tuloksesta. Näin ollenbinaarihaku suoritetaan logaritmisessa ajassa, jolloin saadaan o (log n) keskimääräinen tapausteho.
Mitä eroa on binäärihaulla ja lineaarisella haulla?
Vaikka sekä lineaarinen haku että binäärihaku ovat hakumenetelmiä, niillä on useita eroja. Vaikka binaarihaku toimii lajitelluissa luetteloissa, linjaliikennehaku voi toimia myös lajittelemattomissa luetteloissa. Luettelon lajittelun keskimääräinen tapauksen monimutkaisuus on n log n. lineaarinen haku on yksinkertainen ja suoraviivainen kuin binäärihaku. Lineaarinen haku on kuitenkin liian hidas käytettäväksi suurten luetteloiden kanssa sen o (n) keskimääräisen tapaustuloksen vuoksi. Toisaalta binäärihakua pidetään tehokkaampana menetelmänä, jota voitaisiin käyttää suurten luetteloiden kanssa. Binaarihaun toteuttaminen voi kuitenkin olla melko hankalaa, ja tutkimus on osoittanut, että tarkka koodi binäärihakua varten löytyy vain viidestä kahdestakymmenestä kirjasta.
