close

Binair zoekalgoritme (Binary Search) in PHP: uitleg, stappen en voorbeeld

Het binaire zoekalgoritme is een efficiënte methode om een ​​specifieke waarde in een gesorteerde array te vinden. Deze benadering verdeelt de array in kleinere delen en vergelijkt voortdurend de waarde op de middelste positie van het zoekbereik met de doelwaarde. Als de waarden overeenkomen, wordt de gewenste waarde gevonden; anders blijft het algoritme het zoekbereik verkleinen en herhaalt het proces totdat de waarde is gevonden of er geen elementen meer over zijn om te onderzoeken.

Stappen:

  1. Initialiseer het zoekbereik: Begin met het selecteren van het zoekbereik van de eerste positie left  tot de laatste positie right  van de array.
  2. Vind het middelpunt: Bereken het middelpunt door middel van de left en juiste posities; dit is het middelpunt van het zoekbereik.
  3. Waarden vergelijken: vergelijk de waarde op het middelpunt met de doelwaarde.
  4. Vergelijkingsresultaat verwerken: als de waarde op het middelpunt overeenkomt met de doelwaarde, geeft u deze positie terug. Als de waarde op het middelste punt kleiner is dan de doelwaarde, update dan de linkerpositie naar midden + 1 om de rechterhelft te doorzoeken. Als de waarde op het middelste punt groter is dan de doelwaarde, werkt u de rechterpositie bij naar midden- 1 om de linkerhelft te doorzoeken.
  5. Herhalen: Herhaal stap 2 tot en met 4 totdat de waarde is gevonden of er geen elementen meer zijn om te controleren left > right.

Voor-en nadelen

Voordelen:

  • Efficiënte prestaties: de tijdscomplexiteit van het algoritme is O(log n), waardoor het zeer efficiënt is voor het verwerken van grote datasets.
  • Effectief voor grote datasets: Binair zoeken is effectief in het verminderen van het aantal elementen dat snel moet worden onderzocht voor grote datasets.

Nadelen:

  • Alleen van toepassing op gesorteerde arrays: het algoritme werkt alleen op gesorteerde arrays.
  • Variabel aantal stappen: het aantal stappen dat nodig is om de waarde te vinden, hangt af van de positie in de array en er kunnen veel stappen nodig zijn voor waarden aan de uiteinden.

Voorbeeld: binair zoeken voor het vinden van de waarde 12 in een gesorteerde array in 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.";  
}

Uitleg van het voorbeeld

  1. We beginnen met het initiële zoekbereik van de eerste positie left = 0 tot de laatste positie right = 6  van de array.
  2. We berekenen het middelpunt(midden) door de linker- en rechterposities te middelen; mid = 3. De waarde in het midden is 12.
  3. We vergelijken de waarde bij mid(12) met de doelwaarde(12) en vinden een match, dus we geven positie 3 terug.
  4. Het algoritme eindigt en we voeren het resultaat "Waarde 12 gevonden op positie 3" uit.