Indholdsfortegnelse:
Definition - Hvad betyder binær søgning?
En binær søgealgoritme bruges til at finde placeringen af en bestemt værdi indeholdt i en sorteret matrix. Arbejdet med princippet om kløft og erobring kan denne søgealgoritme være ret hurtig, men det gælder, at dataene skal være i en sorteret form. Det fungerer ved at starte søgningen i midten af matrixen og arbejde ned ad den første nederste eller øverste halvdel af sekvensen. Hvis medianværdien er lavere end målværdien, betyder det, at søgningen skal gå højere, hvis ikke, skal den se på den faldende del af matrixen.
En binær søgning er også kendt som en halvintervalsøgning eller logaritmisk søgning.
Techopedia forklarer Binary Search
En binær søgning er en hurtig og effektiv metode til at finde en bestemt målværdi fra et sæt bestilte varer. Ved at starte midt i den sorterede liste kan den effektivt skære søgerummet i halve ved at bestemme, om listen skal stige op eller ned på baggrund af medianværdien sammenlignet med målværdien.
For eksempel med en målværdi på 8 og et søgeområde på 1 til 11:
- Median / middelværdien findes, og markøren indstilles der, hvilket i dette tilfælde er 6.
- Målet på 8 sammenlignes med 6. Da 6 er mindre end 8, skal målet være i den højere halvdel.
- Markøren flyttes til den næste værdi (7) og sammenlignes med målet. Den er mindre, derfor flytter markøren til den næste højere værdi.
- Markøren er nu på 8. Sammenlignes dette med målet, er det en nøjagtig match, derfor er målet fundet.
Ved hjælp af binær søgning måtte målet kun sammenlignes med tre værdier. Sammenlignet med at udføre en lineær søgning, ville det have startet fra den allerførste værdi og flyttet op, og det er nødvendigt at sammenligne målet med otte værdier. En binær søgning er kun mulig med et bestilt datasæt; hvis dataene er tilfældigt arrangeret, ville en lineær søgning give resultater hele tiden, mens en binær søgning sandsynligvis ville sidde fast i en uendelig sløjfe.
