Binært søk vs Lineært søk
Lineært søk, også kjent som sekvensielt søk, er den enkleste søkealgoritmen. Den søker etter en spesifisert verdi i en liste ved å sjekke hvert element i listen. Binært søk er også en metode som brukes til å finne en spesifisert verdi i en sortert liste. Binær søkemetode halverer antall kontrollerte elementer (i hver iterasjon), noe som reduserer tiden det tar å finne det gitte elementet i listen.
Hva er lineært søk?
Lineært søk er den enkleste søkemetoden, som sjekker hvert element i en liste sekvensielt til det finner et spesifisert element. Inndataene til den lineære søkemetoden er en sekvens (som en matrise, samling eller en streng) og elementet som må søkes. Utdata er sant hvis det spesifiserte elementet er innenfor den angitte sekvensen eller usant hvis det ikke er i sekvensen. Siden denne metoden sjekker hvert element i listen til det spesifiserte elementet er funnet, vil den i verste fall gå gjennom alle elementene i listen før den finner det nødvendige elementet. Kompleksiteten til lineært søk er o(n). Derfor anses det å være for tregt til å brukes når du søker etter elementer i store lister. Men dette er veldig enkelt og enklere å implementere.
Hva er binært søk?
Binært søk er også en metode som brukes til å finne et spesifisert element i en sortert liste. Denne metoden starter med å sammenligne det søkte elementet med elementene i midten av listen. Hvis sammenligningen bestemmer at de to elementene er like, stopper metoden og returnerer posisjonen til elementet. Hvis det søkte elementet er større enn det midterste elementet, starter det metoden igjen med kun den nederste halvdelen av den sorterte listen. Hvis det søkte elementet er mindre enn det midterste elementet, starter det metoden igjen med kun den øverste halvdelen av den sorterte listen. Hvis det søkte elementet ikke er i listen, vil metoden returnere en unik verdi som indikerer det. Derfor halverer den binære søkemetoden antallet elementer sammenlignet (i hver iterasjon), avhengig av resultatet av sammenligningen. Følgelig kjører binært søk i logaritmisk tid, noe som resulterer i o(log n) gjennomsnittlig kasusytelse.
Hva er forskjellen mellom binært søk og lineært søk?
Selv om både lineært søk og binært søk er søkemetoder, har de flere forskjeller. Mens binært søk opererer på sorterte lister, kan linjesøk også operere på usorterte lister. Sortering av en liste har generelt en gjennomsnittlig sakskompleksitet på n log n. lineært søk er enkelt og greit å implementere enn det binære søket. Men lineært søk er for sakte til å brukes med store lister på grunn av dets o(n) gjennomsnittlige saksytelse. På den annen side anses binært søk å være en mer effektiv metode som kan brukes med store lister. Men å implementere det binære søket kan være ganske vanskelig, og en studie har vist at den nøyaktige koden for binært søk kunne finnes i bare fem av tjue bøker.
