close

Algoritem binarnega iskanja (Binary Search) v PHP: razlaga, koraki in primer

Algoritem binarnega iskanja je učinkovita metoda za iskanje določene vrednosti v razvrščeni matriki. Ta pristop razdeli matriko na manjše dele in nenehno primerja vrednost na srednjem položaju iskalnega obsega s ciljno vrednostjo. Če se vrednosti ujemajo, je želena vrednost najdena; v nasprotnem primeru algoritem nadaljuje z oženjem obsega iskanja in ponavlja postopek, dokler ni najdena vrednost ali ni več elementov za pregled.

Koraki:

  1. Inicializirajte obseg iskanja: Začnite z izbiro obsega iskanja od prvega left  do zadnjega položaja right  matrike.
  2. Poiščite srednjo točko: izračunajte srednjo točko tako, da izračunate povprečje left položajev in desno; to je srednja točka obsega iskanja.
  3. Primerjaj vrednosti: primerjajte vrednost na srednji točki s ciljno vrednostjo.
  4. Rezultat primerjave ročaja: Če se vrednost na srednji točki ujema s ciljno vrednostjo, vrnite ta položaj. Če je vrednost na srednji točki manjša od ciljne vrednosti, posodobite levi položaj na sredino + 1, da poiščete desno polovico. Če je vrednost na srednji točki večja od ciljne vrednosti, posodobite desni položaj na sredino- 1 za iskanje po levi polovici.
  5. Ponavljanje: Ponavljajte korake od 2 do 4, dokler ni vrednost najdena ali ni več elementov za preverjanje left > right.

Prednosti in slabosti

Prednosti:

  • Učinkovito delovanje: Časovna zapletenost algoritma je O(log n), zaradi česar je zelo učinkovit za obdelavo velikih naborov podatkov.
  • Učinkovito za velike nabore podatkov: Binarno iskanje je učinkovito pri zmanjševanju števila elementov, ki jih je treba hitro pregledati za velike nabore podatkov.

Slabosti:

  • Velja samo za razvrščene nize: Algoritem deluje samo na razvrščene nize.
  • Spremenljivo število korakov: število korakov, potrebnih za iskanje vrednosti, je odvisno od njenega položaja v matriki in lahko traja veliko korakov za vrednosti blizu koncev.

Primer: binarno iskanje za iskanje vrednosti 12 v razvrščeni matriki v 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.";  
}

Razlaga primera

  1. Začnemo z začetnim iskalnim obsegom od prvega položaja left = 0 do zadnjega položaja right = 6  matrike.
  2. Srednjo točko(mid) izračunamo s povprečenjem leve in desne lege; mid = 3. Vrednost na sredini je 12.
  3. Primerjamo vrednost pri mid(12) s ciljno vrednostjo(12) in najdemo ujemanje, tako da vrnemo položaj 3.
  4. Algoritem se konča in izpišemo rezultat "Vrednost 12 najdena na položaju 3."