close

Dvejetainės paieškos (Binary Search) algoritmas PHP: paaiškinimas, žingsniai ir pavyzdys

Dvejetainės paieškos algoritmas yra efektyvus būdas rasti konkrečią reikšmę surūšiuotame masyve. Šis metodas padalija masyvą į mažesnes dalis ir nuolat lygina reikšmę vidurinėje paieškos diapazono padėtyje su tiksline verte. Jei reikšmės sutampa, randama norima reikšmė; kitu atveju algoritmas toliau siaurina paieškos diapazoną ir kartoja procesą tol, kol randama reikšmė arba nebelieka nagrinėti elementų.

Veiksmai:

  1. Inicijuoti paieškos diapazoną: pradėkite pasirinkdami paieškos diapazoną nuo pirmosios left  iki paskutinės right  masyvo pozicijos.
  2. Raskite vidurinį tašką: Apskaičiuokite vidurinį tašką, vidurkį left ir dešinėje padėtyje; tai yra vidurinis paieškos diapazono taškas.
  3. Palyginti reikšmes: palyginkite vertę viduriniame taške su tiksline verte.
  4. Palyginimo rezultatas: jei vertė viduriniame taške sutampa su tiksline verte, grąžinkite šią poziciją. Jei vertė viduriniame taške yra mažesnė už tikslinę vertę, atnaujinkite kairiąją padėtį į vidurį + 1, kad ieškotumėte dešinėje pusėje. Jei vertė viduriniame taške yra didesnė už tikslinę vertę, atnaujinkite dešinę padėtį į vidurinę – 1, kad ieškotumėte kairiojoje pusėje.
  5. Pakartokite: kartokite 2–4 veiksmus, kol bus rasta reikšmė arba nebeliks tikrintinų elementų left > right.

Privalumai ir trūkumai

Privalumai:

  • Efektyvus našumas: algoritmo sudėtingumas laike yra O(log n), todėl jis yra labai efektyvus tvarkant didelius duomenų rinkinius.
  • Veiksminga dideliems duomenų rinkiniams: Dvejetainė paieška veiksmingai sumažina elementų, kuriuos reikia greitai ištirti dideliems duomenų rinkiniams, skaičių.

Trūkumai:

  • Taikoma tik surūšiuotiems masyvams: algoritmas veikia tik surūšiuotuose masyvuose.
  • Kintamasis žingsnių skaičius: veiksmams, kurių reikia norint rasti reikšmę, skaičius priklauso nuo jos padėties masyve ir gali užtrukti daug veiksmų, kai reikšmės yra netoli galų.

Pavyzdys: dvejetainė paieška, norint rasti 12 reikšmę surūšiuotame PHP masyve 

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.";  
}

Pavyzdžio paaiškinimas

  1. Pradedame nuo pradinio paieškos diapazono nuo pirmosios left = 0 iki paskutinės right = 6  masyvo pozicijos.
  2. Vidurinį tašką(vidurį) apskaičiuojame suvidurkindami kairiąją ir dešinę padėtį; mid = 3. Vertė viduryje yra 12.
  3. Palyginame reikšmę mid(12) su tiksline reikšme(12) ir randame atitiktį, todėl grąžiname 3 poziciją.
  4. Algoritmas baigiasi ir mes išvedame rezultatą „12 reikšmė rasta 3 padėtyje“.