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. Metoden for binær søk halverer antall kontrollerte elementer (i hver iterasjon), og 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. Inngangen til den lineære søkemetoden er en sekvens (for eksempel en matrise, samling eller en streng) og elementet som må søkes. Utdataene er sanne 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 angitte elementet er funnet, vil det i verste fall gå gjennom alle elementene i listen før den finner det nødvendige elementet. Kompleksiteten ved lineært søk er o (n). Derfor anses det å være for sakte 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 elementets posisjon. Hvis det søkte elementet er større enn det midterste elementet, starter metoden på nytt ved å bare bruke den nederste halvdelen av den sorterte listen. Hvis det søkte elementet er mindre enn det midterste elementet, starter metoden på nytt med bare den øverste halvdelen av den sorterte listen. Hvis det søkte elementet ikke er innenfor listen, vil metoden returnere en unik verdi som indikerer at. Derfor halverer den binære søkemetoden antall elementer som er sammenlignet (i hver iterasjon), avhengig av resultatet av sammenligningen. Følgeligbinært søk kjører i logaritmisk tid og resulterer i o (log n) gjennomsnittlig saksytelse.
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 fungerer på sorterte lister, kan linjesøk også fungere på usorterte lister. Sortering av en liste har vanligvis 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 tregt til å brukes med store lister på grunn av o (n) gjennomsnittlig 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 undersøkelse har vist at den nøyaktige koden for binært søk bare finnes i fem av tjue bøker.
