Innan vi lär oss binär sökning, låt oss lära oss:
Vad är sökning?
Sök är ett verktyg som gör det möjligt för användaren att 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 det för användaren. På detta 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 innefattar att dela data i listan till hälften tills det önskade värdet lokaliseras och visas för användaren i sökresultatet. Binär sökning är allmänt känd som en halvintervallssökning eller en logaritmisk sökning .
I denna algoritmhandledning lär du dig:
- Vad är sökning?
- Vad är binär sökning?
- Hur fungerar binär sökning?
- Exempel på binär sökning
- Varför behöver vi binär sökning?
Hur fungerar binär sökning?
Den binära sökningen fungerar på följande sätt:
- Sökprocessen initieras genom att lokalisera mittelementet i den sorterade dataarrayen
- Därefter jämförs nyckelvärdet med elementet
- Om nyckelvärdet är mindre än det mellersta elementet analyseras 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
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 önskat ord.
Ovanstående bild illustrerar följande:
- Du har en matris med 10 siffror och elementet 59 måste hittas.
- Alla element är markerade med index från 0 - 9. Nu beräknas mitten av matrisen. För att göra det tar du indexets vänster- och högervärde och delar dem med 2. Resultatet är 4,5, men vi tar golvvärdet. Därför är mitten 4.
- Algoritmen släpper alla element från mitten (4) till den lägsta gränsen eftersom 59 är större än 24, och nu är matrisen kvar med endast 5 element.
- Nu är 59 större än 45 och mindre än 63. Mitten är 7. Därför blir det högra indexvärdet mitt - 1, vilket är lika med 6, och det vänstra indexvärdet förblir detsamma som tidigare, vilket är 5.
- Vid denna tidpunkt vet du att 59 kommer efter 45. Därför blir det vänstra indexet, som är 5, också mitt.
- Dessa iterationer fortsätter tills matrisen reduceras till endast ett element, eller om objektet som ska hittas blir mitten av matrisen.
Exempel 2
Låt oss titta på följande exempel för att förstå hur binär sökning fungerar
- Du har en rad sorterade värden från 2 till 20 och måste hitta 18.
- Medelvärdet för de nedre och övre gränserna är (l + r) / 2 = 4. Värdet som söks är större än mitten som är 4.
- Matrisvärdena mindre än mitten släpps från sökningen och värden som är större än mittvärdet 4 söks.
- Detta är en återkommande delningsprocess tills det faktiska objektet 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ändas som sökalgoritm:
- Binär sökning fungerar effektivt på sorterad data oavsett storleken på datan
- 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 önskade elementet. Detta gör sökcyklerna kortare och mer exakta.
- Binär sökning utför jämförelser av de sorterade uppgifterna baserat på en beställningsprincip än att använda jämställdhetsjämförelser, som är långsammare och mestadels felaktiga.
- Efter varje sökcykel delar algoritmen storleken på matrisen i hälften, och i nästa iteration fungerar den bara i den återstående halvan av matrisen
Sammanfattning
- Sök är ett verktyg som gör det möjligt för användaren att söka efter dokument, filer och andra typer av data. 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.
- Binär sökning är allmänt känd som en halvintervallssökning eller en logaritmisk sökning
- Det fungerar genom att dela upp matrisen i hälften på varje iteration under det nödvändiga elementet finns.
- Den binära algoritmen tar mitten av matrisen genom att dela summan av de vänstra och högra indexvärdena med 2. Nu tappar algoritmen antingen den nedre eller övre gränsen för element från mitten av matrisen, beroende på vilket element som ska .
- Algoritmen får slumpmässigt åtkomst till data för att hitta önskat element. Detta gör sökcyklerna kortare och mer exakta.
- Binär sökning utför jämförelser av de sorterade uppgifterna baserat på en beställningsprincip än att använda jämställdhetsjämförelser som är långsamma och felaktiga.
- En binär sökning är inte lämplig för osorterad data.