Linear søk og binær søk er vanlige algoritmer som brukes til å finne elementer i en liste. Forstå det forventede antall sammenligninger hver algoritme gjør kan hjelpe til med å velge den mest effektive metoden for bestemte situasjoner. Denne artikkelen sammenligner de forventede sammenligningene i lineære versus binære søkemetoder.

Linjesøk

Linjesøk kontrollerer hvert element i listen sekvensielt til det finner målet eller når slutten. Det forventede antall sammenligninger avhenger av om målet er tilstede og dens posisjon i listen.

Hvis listen inneholder n elementer og målet er like sannsynlig å være i alle posisjoner, er det forventede antall sammenligninger:

Utviklede sammenligninger = (n + 1) / 2]

Dette skyldes i gjennomsnitt at søket vil finne målet halvveis gjennom listen.

Binærsøk

Binærsøk fungerer på sorterte lister ved å dele søkeintervallet i to. Effektiviteten avhenger av listens størrelse og plasseringen av målet.

I det beste tilfellet er målet på midten, som krever bare én sammenligning. I verste tilfelle tar det omtrent ]log]2 n sammenligninger.

Hvis målet er like sannsynlig å være i alle stillinger, er det forventede antall sammenligninger omtrent:

Utviklede sammenligninger ⁇ log2] n]

Sammendrag

  • Linjesøk har forventet sammenligningstall (n + 1) / 2.
  • Binærsøk har et forventet sammenlikningstall på omtrentlig log]2 n.
  • Binærsøk krever generelt færre sammenligninger for store lister.
  • Linjesøk kan være foretrukket for små eller usorterte lister.