Lineaarinen haku ja binary haku ovat yhteisiä algoritmeja käytetään löytämään elementtejä luettelosta. Ymmärtäminen odotettu määrä vertailuja kunkin algoritmin tekee voi auttaa valitsemaan tehokkain menetelmä tietyissä tilanteissa. Tämä artikkeli vertaa odotettuja vertailuja lineaarisen vs. binary hakumenetelmiä.

Lineaarinen haku

Lineaarinen haku tarkistaa jokaisen luettelon osan peräkkäin, kunnes se löytää kohteen tai saavuttaa sen. Odotettavissa oleva vertailujen määrä riippuu siitä, onko kohde olemassa ja onko se luettelossa.

Jos luettelo sisältää n elementtejä ja tavoite on yhtä todennäköisesti missä tahansa asennossa, vertailujen odotettu määrä on:

Edelliset vertailut = (n + 1) / 2

Tämä johtuu siitä, että keskimäärin haku löytää kohteen puolivälissä listaa.

Binaarihaku

Binary-haku toimii lajitelluilla luetteloilla jakamalla hakuväli toistuvasti kahtia. Sen tehokkuus riippuu luettelon koosta ja kohteen sijainnista.

Parhaassa tapauksessa tavoite on keskellä, vaatii vain yhden vertailun. Pahimmassa tapauksessa se kestää noin log2 n vertailuja.

Jos oletetaan, että tavoite on yhtä todennäköisesti missä tahansa asennossa, vertailujen määräksi odotetaan suunnilleen:

]Oletetut vertailut ... loki[2 n

Vertailun yhteenveto

  • Lineaarinen haku on odotettu vertailuluku (n + 1) / 2.
  • Binäärihaun vertailuluku on noin log2 n.
  • Binary-haku edellyttää yleensä vähemmän vertailuja suurille luetteloille.
  • Lineaarinen haku voi olla parempi pienille tai lajittelemattomille luetteloille.