Forskjell mellom binær søk og linjær søk

Binær søk vs Linjær søk

Linjært søk, også kjent som sekvensielt søk, er den enkleste søkalgoritmen. Den søker etter en spesifisert verdi i en liste ved å merke 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 elementer som er kontrollert (i hver iterasjon), og reduserer tiden som er tatt for å finne det oppgitte elementet i listen.

Hva er Linear Search?

Linjært søk er den enkleste søkemetoden, som kontrollerer hvert element i en liste i rekkefølge til den 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. Utgangen er sant hvis det angitte elementet er innenfor den angitte sekvensen eller falsk hvis den ikke er i sekvensen. Siden denne metoden kontrollerer hvert element i listen til det angitte elementet er funnet, vil det i verste fall gå gjennom alle elementene i listen før det finner det nødvendige elementet. Kompleksiteten til lineær søk er o (n). Derfor anses det å være for sakte å bli brukt når man søker elementer i store lister. Men dette er veldig enkelt og enklere å implementere.

Hva er binær søk?

Binær søk er også en metode som brukes til å finne et spesifisert element i en sortert liste. Denne metoden starter ved å sammenligne det søkte elementet med elementene midt på 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 mellomelementet, starter det metoden igjen med bare den nederste halvdelen av sortert liste. Hvis det søkte elementet er mindre enn mellomelementet, starter det metoden igjen med bare den øverste halvdelen av sorteringslisten. Hvis det søkte elementet ikke er innenfor listen, returnerer metoden en unik verdi som indikerer det. Derfor binær søkemetoden halverer antall elementer sammenlignet (i hver iterasjon), avhengig av resultatet av sammenligningen. Følgelig går binær søk i logaritmisk tid som resulterer i o (log n) gjennomsnittlig case-ytelse.

Hva er forskjellen mellom binær søk og linjær søk?

Selv om både lineært søk og binært søk søker metoder har de flere forskjeller. Mens binær søk opererer på sorterte lister, kan liner-søk også operere på usorterte lister. Sortering av en liste har generelt en gjennomsnittlig sakskompleksitet av n log n. lineær søk er enkel og grei å implementere enn binær søk. Men lineært søk er for sakte for å bli brukt med store lister på grunn av sin o (n) gjennomsnittlige case-ytelse.På den annen side anses binær søk å være en mer effektiv metode som kan brukes med store lister. Men implementering av binærsøk kan være ganske vanskelig, og en studie har vist at den nøyaktige koden for binær søk kunne bli funnet i bare fem av tyve bøker.