Binær søgealgoritme med EKSEMPEL

Før vi lærer binær søgning, lad os lære, hvad søgning er.

Hvad er søgning?

Søg er et værktøj, der gør det muligt for brugeren at finde dokumenter, filer, medier eller enhver anden type data, der opbevares i en database. Søgning fungerer efter det simple princip at matche kriterierne med posterne og vise dem til brugeren. På denne måde fungerer den mest basale søgefunktion.

Hvad er binær søgning?

En binær søgning er en avanceret type søgealgoritme, der finder og henter data fra en sorteret liste over elementer. Dens centrale arbejdsprincip involverer at dele dataene i listen i to halvdele, indtil den ønskede værdi er fundet og vist for brugeren i søgeresultatet. Binær søgning er almindeligvis kendt som en halvintervalsøgning eller logaritmisk søgning.

Hvordan fungerer binær søgning?

Den binære søgning fungerer på følgende måde:

• Søgeprocessen starter ved at finde det midterste element i den sorterede datamatrix.
• Derefter sammenlignes nøgleværdien med elementet.
• Hvis nøgleværdien er mindre end det midterste element, analyserer søgningen de øvre værdier til det midterste element med henblik på sammenligning og matchning.
• Hvis nøgleværdien er større end det midterste element, analyserer søgningen de lavere værdier til det midterste element med henblik på sammenligning og matchning.

Binær søgealgoritme (pseudokode)

Den binære søgning kan skrives som en kort, iterativ rutine. Den beholder to pointere, en lav og en høj, og indsnævrer området, indtil målet er fundet, eller området bliver 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 succes og -1, når værdien ikke er til stede. Da området halveres ved hver gennemløb, kører løkken højst log₂(n) gange.

Eksempel på binær søgning

Lad os se på eksemplet med en ordbog. Hvis du har brug for at finde et bestemt ord, går ingen igennem hvert ord på en sekventiel måde, men finder tilfældigt de nærmeste ord for at søge efter det påkrævede ord.

Ovenstående billede illustrerer følgende:

1. Du har en matrix på 10 cifre, og elementet 59 skal findes.
2. Alle elementerne er markeret med et indeks fra 0 til 9. Nu beregnes midten af ​​arrayet. For at gøre dette tager du de venstre og højre værdier af indekset og dividerer dem med 2. Resultatet er 4.5, men vi tager gulvværdien. Derfor er midten 4.
3. Algoritmen fjerner alle elementerne fra midten (4) til den laveste grænse, fordi 59 er større end 24, og nu er arrayet tilbage med kun 5 elementer.
4. Nu er 59 større end 45 og mindre end 63. Midten er 7. Derfor bliver den højre indeksværdi midterste − 1, hvilket er lig med 6, og den venstre indeksværdi forbliver den samme som før, hvilket er 5.
5. På dette tidspunkt ved du, at 59 kommer efter 45. Derfor bliver venstre indeks, som er 5, også midten.
6. Disse iterationer fortsætter, indtil arrayet er reduceret til kun ét element, eller det element, der skal findes, bliver midten af ​​arrayet.

Eksempel 2

Lad os se på følgende eksempel for at forstå, hvordan binær søgning fungerer.

1. Du har en række sorterede værdier fra 2 til 20 og skal finde 18.
2. Gennemsnittet af den nedre og øvre grænse er (l + r) / 2 = 4. Den søgede værdi er større end midterværdien, som er 4.
3. Arrayværdier mindre end midtværdien udelades fra søgningen, og værdier større end midtværdien 4 søges i.
4. Dette er en tilbagevendende opdelingsproces, indtil det faktiske emne, der skal søges, er fundet.

Hvorfor har vi brug for binær søgning?

Følgende grunde gør binær søgning til et bedre valg som søgealgoritme:

• Binær søgning fungerer effektivt på sorterede data uanset datastørrelsen.
• I stedet for at udføre søgningen ved at gennemgå dataene i en sekvens, får den binære algoritme tilfældigt adgang til dataene for at finde det nødvendige element. Dette gør søgecyklusserne kortere og mere nøjagtige.
• Binær søgning udfører sammenligninger af de sorterede data baseret på et sorteringsprincip i stedet for at bruge lighedssammenligninger, som er langsommere og for det meste unøjagtige.
• Efter hver søgecyklus deler algoritmen størrelsen af ​​arrayet i to halvdele; derfor vil den i den næste iteration kun virke i den resterende halvdel af arrayet.

Lær vores næste vejledning om Lineær søgning: Python, C++ Eksempel.

Binær søgning vs. lineær søgning

Binær søgning og lineær søgning er de to mest almindelige måder at finde en værdi i en samling på. Tabellen nedenfor fremhæver, hvordan de adskiller sig:

Kort sagt er binær søgning meget hurtigere på store sorterede data, mens lineær søgning er enklere og den eneste mulighed, når dataene ikke er sorteret.

Ofte Stillede Spørgsmål