Hva er et binært søk?

Anta at en person har et veldig stort utvalg av gjenstander og ordner dem på en eller annen ordnet måte i en lang rekke. Den personen kan raskt finne ut hvor i rekken et bestemt objekt befinner seg ved å bruke et binært søk. Dette søket gjøres ved å sjekke det midterste elementet i rekken, og hvis det midtre objektet ikke er det søkte elementet, se deretter bare i en av halvdelene av raden der elementet kan være. Personen ville vite hvilken halvdel han skal fortsette å se på fordi varene er ordnet i orden. Disse to trinnene gjøres om og om igjen, på mindre og mindre halvdeler, til gjenstanden enten blir funnet eller det ikke er noe igjen å se på.

Innen informatikk er et binært søk en trinnvis prosedyre som finner plasseringen eller indeksen til et element i et sekvensvis sortert datasett. Det oppnår dette ved å sammenligne en kjent verdi med et utpekt midtelement i matrisen, og hvis det ikke er ekvivalent, begrenser midtelementets sammenligning gjentatte ganger til den mindre relevante halvdelen av settet til en ekvivalens er oppnådd eller listen er oppbrukt.

Et binært søk, noen ganger kalt et halvt intervallsøk, er mye raskere enn et grunnleggende sekvensielt søk som starter i den ene enden av en liste over elementer og sammenligner hvert element underveis til en kamp blir funnet eller til søket når slutten av listen. Hvis en person hadde 100 elementer på rad, og den siste varen ble det som ble sett etter, ville et sekvensielt søk 100 sammenligninger. Halveringsmetoden krever imidlertid bare syv sammenligninger maksimalt før gjenstanden blir funnet. Det er tydeligvis mye mer effektivt enn et sekvensielt søk.

Den største ulempen med et binært søk er at listen over elementer må sorteres for at dette søket skal fungere. Det tar tid å sortere en liste. Det kan ta mer tid å sortere å bruke denne typen søk enn å gjøre en annen type søk i utgangspunktet.

Å kunne bruke informasjon, spesielt fra veldig store datasett, er viktig for å utføre mange oppgaver i livet. Datafagens fagfelt omhandler mange typer problemer, inkludert å finne effektive måter å søke etter informasjon slik at nyttige resultater oppnås. Et binært søk er bare en av mange algoritmer som er tilgjengelige for å søke gjennom data.