Innehållsförteckning:
Definition - Vad betyder Binary Search?
En binär sökalgoritm används för att hitta positionen för ett specifikt värde som finns i en sorterad matris. Arbetar med principen att dela och erövra kan denna sökalgoritm vara ganska snabb, men varning är att uppgifterna måste vara i en sorterad form. Det fungerar genom att starta sökningen i mitten av matrisen och arbeta ner den första nedre eller övre halvan av sekvensen. Om medianvärdet är lägre än målvärdet, betyder det att sökningen måste gå högre, om inte, måste den titta på den fallande delen av matrisen.
En binär sökning är också känd som en halvintervallsökning eller logaritmisk sökning.
Techopedia förklarar Binary Search
En binär sökning är en snabb och effektiv metod för att hitta ett specifikt målvärde från en uppsättning beställda artiklar. Genom att börja i mitten av den sorterade listan kan den effektivt skära ut sökutrymmet i hälften genom att bestämma om listan ska gå upp eller ner baserat på medianvärdet jämfört med målvärdet.
Till exempel med ett målvärde på 8 och ett sökutrymme på 1 till 11:
- Median / mittvärdet hittas och pekaren ställs in där, som i detta fall är 6.
- Målet på 8 jämförs med 6. Eftersom 6 är mindre än 8 måste målet vara i den högre halvan.
- Pekaren flyttas till nästa värde (7) och jämförs med målet. Den är mindre, därför flyttar pekaren till nästa högre värde.
- Pekaren är nu på 8. Jämför detta med målet, det är en exakt matchning, därför har målet hittats.
Med hjälp av binär sökning måste målet bara jämföras med tre värden. Jämfört med att göra en linjär sökning skulle det ha börjat från det första värdet och flyttat upp och behövt jämföra målet med åtta värden. En binär sökning är endast möjlig med en beställd datauppsättning; om uppgifterna är slumpmässigt ordnade skulle en linjär sökning ge resultat hela tiden medan en binär sökning troligen skulle fastna i en oändlig slinga.
