Ero binaarisen ja lineaarisen haun välillä

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 luettelon kaikki elementit. Binaarihaku on myös menetelmä, jota käytetään tietyn arvon löytämiseen lajitelluissa luetteloissa. Binaarinen hakumenetelmä puolittaa tarkistettujen elementtien määrän (jokaisessa iteraatiossa) vähentäen tietyn kohteen luetteloon löytämiseen kuluvaa aikaa luettelossa.

Mikä on lineaarinen haku?

Lineaarinen haku on yksinkertaisin hakumenetelmä, joka tarkistaa luettelon jokaisen elementin peräkkäin, kunnes se löytää määritetyn elementin. Syöttö lineaariseen hakumenetelmään on sekvenssi (kuten taulukko, kokoelma tai merkkijono) ja etsittävä kohde. Tulos on totta, jos määritetty kohde on annetun sekvenssin sisällä, tai väärä, jos se ei ole sekvenssissä. Koska tämä menetelmä tarkistaa kaikki luettelon kohteet, kunnes määritetty kohde löytyy, pahimmassa tapauksessa se käy läpi kaikki luettelon elementit ennen kuin se löytää vaaditun elementin. Lineaarisen haun monimutkaisuus on o (n). Siksi sitä pidetään liian hitaana käytettäväksi etsiessäsi elementtejä suurista luetteloista. Mutta tämä on hyvin yksinkertaista ja helpompaa toteuttaa.

Mikä on binaarihaku?

Binaarihaku on myös menetelmä, jota käytetään tietyn kohteen löytämiseen lajitelluissa luetteloissa. Tämä menetelmä alkaa vertaamalla etsittyä elementtiä luettelon keskellä oleviin elementteihin. Jos vertailu osoittaa, että kaksi elementtiä ovat samat, menetelmä pysähtyy ja palauttaa elementin sijainnin. Jos etsitty elementti on suurempi kuin keskielementti, se aloittaa menetelmän uudelleen käyttämällä vain lajitellun luettelon alaosaa. Jos etsitty elementti on pienempi kuin keskielementti, se aloittaa menetelmän uudelleen käyttämällä vain lajitellun listan yläosaa. Jos etsitty elementti ei ole luettelossa, menetelmä palauttaa sen osoittavan yksilöllisen arvon. Siksi binaarinen hakumenetelmä puolittaa vertailtavien elementtien määrän (jokaisessa iteraatiossa) vertailun tuloksesta riippuen. Tämän seurauksena binaarihaku suoritetaan logaritmisessa ajassa, jolloin saadaan o (log n) tapauksen keskimääräinen suorituskyky.

Mitä eroa on binaarisen haun ja lineaarisen haun välillä??

Vaikka sekä lineaarinen haku että binaarinen haku ovat hakumenetelmiä, niillä on useita eroja. Vaikka binaarihaku toimii lajitelluilla luetteloilla, linjahaku voi toimia myös lajittelemattomissa luetteloissa. Luettelon lajittelulla on yleensä keskimääräinen tapaus monimutkaisuus n log n. lineaarinen haku on yksinkertainen ja suoraviivainen toteuttaa kuin binaarihaku. Mutta lineaarinen haku on liian hidas käytettäväksi suurissa luetteloissa johtuen sen o (n) tapauksen keskimääräisestä suorituskyvystä. Toisaalta binääristä hakua pidetään tehokkaampana menetelmänä, jota voidaan käyttää suurten luetteloiden kanssa. Mutta binäärisen haun toteuttaminen voi olla melko hankala, ja tutkimus on osoittanut, että tarkka koodi binäärihaulle löytyy vain viidestä kahdestakymmenestä kirjasta.