Binär sökalgoritm med EXEMPEL

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

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 data i listan till hälften 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 lokalisera mittelementet i den sorterade uppsättningen av data
• Därefter jämförs nyckelvärdet med elementet
• Om nyckelvärdet är mindre än mittelementet, analyserar sökningar de övre värdena till mittelementet för jämförelse och matchning
• Om nyckelvärdet är större än mittelementet, analyserar sökningar de lägre värdena till mittelementet 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 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 – 9. Nu beräknas mitten av arrayen. För att göra det tar du indexets värde längst till vänster och till höger och dividerar dem med 2. Resultatet är 4.5, men vi tar golvvärdet. Därför är mitten 4.
3. Algoritmen sänker alla element från mitten (4) till den lägsta gränsen eftersom 59 är större än 24, och nu har arrayen bara 5 element.
4. Nu är 59 större än 45 och mindre än 63. Mitten ä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 den binära sökningen fungerar

1. Du har en rad sorterade värden från 2 till 20 och måste hitta 18.
2. Genomsnittet av de nedre och övre gränserna är (l + r) / 2 = 4. Värdet som söks är större än mitten som är 4.
3. Matrisvärdena mindre än mitten tas bort från sökningen och värden större än mittvärdet 4 sö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 den binära sökningen till ett bättre val för att användas som en 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 nödvändiga elementet. Detta gör sökcyklerna kortare och mer exakta.
• Binär sökning utför jämförelser av den sorterade datan baserat på en ordningsprincip än att använda jämställdhetsjämförelser, som är långsammare och för det mesta felaktiga.
• Efter varje sökningscykel delar algoritmen upp storleken på arrayen i hälften så i nästa iteration kommer den att fungera endast i den återstående hälften av arrayen

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

Sammanfattning

• Sök är ett verktyg som gör att användaren kan 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 arrayen i hälften vid varje iteration under det nödvändiga elementet hittas.
• Smakämnen binär algoritm tar mitten av arrayen genom att dividera summan av indexvärdena till vänster och längst till höger med 2. Nu sänker algoritmen antingen den nedre eller övre gränsen för element från mitten av arrayen, beroende på vilket element som ska hittas.
• Algoritmen kommer 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 den sorterade datan baserat på en ordningsprincip ä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 osorterade data.