close

Binär sökalgoritm (Binary Search) i PHP: Förklaring, steg och exempel

Algoritmen för binär sökning är en effektiv metod för att hitta ett specifikt värde i en sorterad array. Detta tillvägagångssätt delar upp arrayen i mindre delar och jämför kontinuerligt värdet i mitten av sökintervallet med målvärdet. Om värdena matchar, hittas det önskade värdet; Annars fortsätter algoritmen att begränsa sökintervallet och upprepar processen tills värdet hittas eller inga fler element finns kvar att undersöka.

Steg:

  1. Initiera sökintervallet: Börja med att välja sökintervallet från den första positionen left  till den sista positionen right  i arrayen.
  2. Hitta mittpunkten: Beräkna mittpunkten genom att ta ett medelvärde av left och högra positionerna; detta är mittpunkten i sökintervallet.
  3. Jämför värden: Jämför värdet i mitten med målvärdet.
  4. Hantera jämförelseresultat: Om värdet vid mittpunkten matchar målvärdet, returnera denna position. Om värdet vid mittpunkten är mindre än målvärdet, uppdatera den vänstra positionen till mitten + 1 för att söka den högra halvan. Om värdet vid mittpunkten är större än målvärdet, uppdatera den högra positionen till mitten- 1 för att söka i den vänstra halvan.
  5. Upprepa: Upprepa steg 2 till 4 tills värdet hittas eller det inte finns fler element att kontrollera left > right.

Fördelar och nackdelar

Fördelar:

  • Effektiv prestanda: Algoritmens tidskomplexitet är O(log n), vilket gör den mycket effektiv för att hantera stora datamängder.
  • Effektiv för stora datamängder: Binär sökning är effektiv för att minska antalet element som snabbt ska undersökas för stora datamängder.

Nackdelar:

  • Tillämplig endast på sorterade arrayer: Algoritmen fungerar bara på sorterade arrayer.
  • Variabelt antal steg: Antalet steg som krävs för att hitta värdet beror på dess position i arrayen, och det kan ta många steg för värden nära ändarna.

Exempel: Binär sökning för att hitta värdet 12 i en sorterad array i PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Förklaring av exemplet

  1. Vi börjar med det initiala sökintervallet från den första positionen left = 0 till den sista positionen right = 6  i arrayen.
  2. Vi beräknar mittpunkten(mitten) genom att ta ett medelvärde för vänster och höger position; mid = 3. Värdet vid mitten är 12.
  3. Vi jämför värdet vid mid(12) med målvärdet(12) och hittar en matchning, så vi returnerar position 3.
  4. Algoritmen slutar och vi matar ut resultatet "Värde 12 hittat vid position 3."