Binär sökalgoritm med EXEMPEL

Innan vi lär oss binär sökning, låt oss lära oss vad sökning är.

Vad är Sök?

Sök är ett verktyg som gör att användaren kan hitta dokument, filer, media eller någon annan typ av data som finns i en databas. Sök fungerar på den enkla principen att matcha kriterierna med posterna och visa dem för användaren. På så sätt fungerar den mest grundläggande sökfunktionen.

Vad är binär sökning?

En binär sökning är en avancerad typ av sökalgoritm som hittar och hämtar data från en sorterad lista med objekt. Dess grundläggande arbetsprincip innebär att dela upp informationen i listan i två halvor tills det önskade värdet hittas och visas för användaren i sökresultatet. Binär sökning är allmänt känd som en halvintervallssökning eller ett logaritmisk sökning.

Hur fungerar binär sökning?

Den binära sökningen fungerar på följande sätt:

• Sökprocessen initieras genom att hitta det mittersta elementet i den sorterade datamatrixen.
• Därefter jämförs nyckelvärdet med elementet.
• Om nyckelvärdet är mindre än det mellersta elementet analyserar sökningen de övre värdena till det mellersta elementet för jämförelse och matchning.
• Om nyckelvärdet är större än det mellersta elementet analyserar sökningen de lägre värdena till det mellersta elementet för jämförelse och matchning.

Binär sökalgoritm (pseudokod)

Den binära sökningen kan skrivas som en kort, iterativ rutin. Den behåller två pekare, låg och hög, och begränsar intervallet tills målet hittas eller intervallet 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 returnerar målets index vid framgång och -1 när värdet inte finns. Eftersom intervallet halveras vid varje pass körs loopen högst log₂(n) gånger.

Exempel på binär sökning

Låt oss titta på exemplet på en ordbok. Om du behöver hitta ett visst ord går ingen igenom varje ord på ett sekventiellt sätt utan lokaliserar slumpmässigt de närmaste orden för att söka efter det önskade ordet.

Bilden ovan illustrerar följande:

1. Du har en matris med 10 siffror och elementet 59 måste hittas.
2. Alla element är markerade med index från 0 till 9. Nu beräknas mitten av arrayen. För att göra det tar du indexets vänstra och högra värden och dividerar dem med 2. Resultatet är 4.5, men vi tar golvvärdet. Därför är mitten 4.
3. Algoritmen tar bort alla element från mitten (4) till den lägsta gränsen, eftersom 59 är större än 24, och nu finns det bara 5 element kvar i matrisen.
4. Nu är 59 större än 45 och mindre än 63. Mittvärdet är 7. Därför blir det högra indexvärdet mitten − 1, vilket är lika med 6, och det vänstra indexvärdet förblir detsamma som tidigare, vilket är 5.
5. Vid det här laget vet du att 59 kommer efter 45. Därför blir det vänstra indexet, som är 5, också mitt.
6. Dessa iterationer fortsätter tills arrayen reduceras till endast ett element, eller objektet som ska hittas blir mitt i arrayen.

Exempelvis 2

Låt oss titta på följande exempel för att förstå hur binärsökning fungerar.

1. Du har en rad sorterade värden från 2 till 20 och måste hitta 18.
2. Medelvärdet av den nedre och övre gränsen är (l + r) / 2 = 4. Värdet som söks är större än mittvärdet, vilket är 4.
3. Matrisvärden som är mindre än mittvärdet tas bort från sökningen, och värden som är större än mittvärdet 4 genomsöks.
4. Detta är en återkommande uppdelningsprocess tills det faktiska föremålet som ska sökas hittas.

Varför behöver vi binär sökning?

Följande skäl gör binär sökning till ett bättre val att använda som sökalgoritm:

• Binär sökning fungerar effektivt på sorterade data oavsett datamängd.
• Istället för att utföra sökningen genom att gå igenom data i en sekvens, kommer den binära algoritmen slumpmässigt åt data för att hitta det nödvändiga elementet. Detta gör sökcyklerna kortare och mer exakta.
• Binär sökning utför jämförelser av sorterad data baserat på en ordningsprincip snarare än att använda likhetsjämförelser, vilka är långsammare och mestadels felaktiga.
• Efter varje sökcykel delar algoritmen upp arrayens storlek i hälften; därför kommer den i nästa iteration bara att fungera i den återstående halvan av arrayen.

Läs vår nästa handledning om Linjär sökning: Python, C++ Exempelvis.

Binär sökning kontra linjär sökning

Binär sökning och linjär sökning är de två vanligaste sätten att hitta ett värde i en samling. Tabellen nedan visar hur de skiljer sig åt:

Kort sagt, binär sökning är mycket snabbare på stora sorterade data, medan linjär sökning är enklare och det enda alternativet när data inte är sorterade.

Vanliga frågor