Binær søkealgoritme med EKSEMPEL

Før vi lærer binært søk, la oss lære hva søk er.

Hva er søk?

Søk er et verktøy som gjør det mulig for brukeren å finne dokumenter, filer, media eller andre typer data som holdes inne i en database. Søk fungerer etter det enkle prinsippet å matche kriteriene med postene og vise det til brukeren. På denne måten fungerer den mest grunnleggende søkefunksjonen.

Hva er binært søk?

Et binært søk er en avansert type søkealgoritme som finner og henter data fra en sortert liste over elementer. Kjerneprinsippet for arbeidet innebærer å dele dataene i listen i to til den nødvendige verdien er funnet og vist til brukeren i søkeresultatet. Binært søk er ofte kjent som en halvintervallsøk eller logaritmisk søk.

Hvordan fungerer binært søk?

Det binære søket fungerer på følgende måte:

• Søkeprosessen starter ved å finne det midterste elementet i den sorterte datamatrisen.
• Etter det sammenlignes nøkkelverdien med elementet.
• Hvis nøkkelverdien er mindre enn det midterste elementet, analyserer søket de øvre verdiene til det midterste elementet for sammenligning og matching.
• Hvis nøkkelverdien er større enn det midterste elementet, analyserer søket de lavere verdiene til det midterste elementet for sammenligning og matching.

Binær søkealgoritme (pseudokode)

Det binære søket kan skrives som en kort, iterativ rutine. Den beholder to pekere, lav og høy, og begrenser området til målet er funnet eller området blir tomt.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Rutinen returnerer målets indeks ved suksess, og -1 når verdien ikke finnes. Fordi området halveres ved hver omgang, kjøres løkken maksimalt log₂(n) ganger.

Eksempel på binært søk

La oss se på eksempelet på en ordbok. Hvis du trenger å finne et bestemt ord, går ingen gjennom hvert ord på en sekvensiell måte, men finner tilfeldig de nærmeste ordene for å søke etter det nødvendige ordet.

Bildet ovenfor illustrerer følgende:

1. Du har en matrise med 10 sifre, og elementet 59 må finnes.
2. Alle elementene er merket med indeksen fra 0 til 9. Nå beregnes midten av tabellen. For å gjøre dette tar du verdiene lengst til venstre og lengst til høyre i indeksen og deler dem på 2. Resultatet er 4.5, men vi tar gulvverdien. Derfor er midten 4.
3. Algoritmen fjerner alle elementene fra midten (4) til den laveste grensen, fordi 59 er større enn 24, og nå står matrisen igjen med bare 5 elementer.
4. Nå er 59 større enn 45 og mindre enn 63. Midten er 7. Derfor blir den høyre indeksverdien midtre − 1, som er lik 6, og den venstre indeksverdien forblir den samme som før, som er 5.
5. På dette tidspunktet vet du at 59 kommer etter 45. Derfor blir venstre indeks, som er 5, også midten.
6. Disse iterasjonene fortsetter til matrisen er redusert til bare ett element, eller elementet som skal finnes blir midt i matrisen.

Eksempel 2

La oss se på følgende eksempel for å forstå hvordan binærsøk fungerer.

1. Du har en rekke sorterte verdier fra 2 til 20 og må finne 18.
2. Gjennomsnittet av den nedre og øvre grensen er (l + r) / 2 = 4. Verdien som søkes etter er større enn midten, som er 4.
3. Matriseverdier som er mindre enn midtverdien, fjernes fra søket, og verdier som er større enn midtverdien 4 søkes i.
4. Dette er en gjentakende delingsprosess til det faktiske elementet som skal søkes er funnet.

Hvorfor trenger vi binært søk?

Følgende grunner gjør binært søk til et bedre valg å bruke som en søkealgoritme:

• Binært søk fungerer effektivt på sorterte data uansett datastørrelse.
• I stedet for å utføre søket ved å gå gjennom dataene i en sekvens, får den binære algoritmen tilfeldig tilgang til dataene for å finne det nødvendige elementet. Dette gjør søkesyklusene kortere og mer nøyaktige.
• Binært søk utfører sammenligninger av de sorterte dataene basert på et sorteringsprinsipp i stedet for å bruke likhetssammenligninger, som er tregere og stort sett unøyaktige.
• Etter hver søkesyklus deler algoritmen størrelsen på arrayet i to; derfor vil den i neste iterasjon bare fungere i den gjenværende halvdelen av arrayet.

Lær vår neste veiledning om Lineært søk: Python, C++ Eksempel.

Binært søk vs. lineært søk

Binært søk og lineært søk er de to vanligste måtene å finne en verdi i en samling på. Tabellen nedenfor viser hvordan de skiller seg:

Kort sagt, binært søk er mye raskere på store sorterte data, mens lineært søk er enklere og det eneste alternativet når dataene ikke er sortert.

Spørsmål og svar