Innholdsfortegnelse:
Definisjon - Hva betyr binærsøk?
En binær søkealgoritme brukes til å finne posisjonen til en spesifikk verdi som er inneholdt i en sortert matrise. Arbeidet med prinsippet om å dele og erobre, kan denne søkealgoritmen være ganske rask, men forbeholdet er at dataene må være i en sortert form. Det fungerer ved å starte søket midt i matrisen og jobbe med å gå nedover den første nedre eller øvre halvdel av sekvensen. Hvis medianverdien er lavere enn målverdien, betyr det at søket må gå høyere, hvis ikke, må det se på den synkende delen av matrisen.
Et binært søk er også kjent som et halvintervallsøk eller logaritmisk søk.
Techopedia forklarer Binary Search
Et binært søk er en rask og effektiv metode for å finne en spesifikk målverdi fra et sett med bestilte elementer. Ved å starte midt i den sorterte listen, kan den effektivt kutte søkeområdet i to ved å bestemme om den skal stige opp eller ned på listen basert på medianverdien sammenlignet med målverdien.
For eksempel med en målverdi på 8 og et søkeområde mellom 1 og 11:
- Median- / mellomverdien er funnet og pekeren er satt der, som i dette tilfellet er 6.
- Målet på 8 blir sammenlignet med 6. Siden 6 er mindre enn 8, må målet være i den øvre halvdelen.
- Pekeren flyttes til neste verdi (7) og sammenlignes med målet. Den er mindre, derfor flytter pekeren til neste høyere verdi.
- Pekeren er nå 8. Når du sammenligner dette med målet, er det en nøyaktig match, derfor er målet funnet.
Ved bruk av binærsøk måtte målet bare sammenlignes med tre verdier. Sammenlignet med å gjøre et lineært søk, ville det ha startet fra den første verdien og flyttet opp, og trengt å sammenligne målet med åtte verdier. Et binært søk er bare mulig med et bestilt datasett; Hvis dataene er tilfeldig ordnet, vil et lineært søk gi resultater hele tiden mens et binært søk antagelig ville sitte fast i en uendelig sløyfe.
