close

Algoritmi i Kërkimit Binar (Binary Search) në PHP: Shpjegim, Hapat dhe Shembull

Algoritmi i Kërkimit Binar është një metodë efikase për të gjetur një vlerë specifike në një grup të renditur. Kjo qasje e ndan grupin në pjesë më të vogla dhe krahason vazhdimisht vlerën në pozicionin e mesit të diapazonit të kërkimit me vlerën e synuar. Nëse vlerat përputhen, gjendet vlera e dëshiruar; përndryshe, algoritmi vazhdon të ngushtojë diapazonin e kërkimit dhe e përsërit procesin derisa të gjendet vlera ose të mos mbeten më elementë për t'u ekzaminuar.

Hapat:

  1. Inicializimi i gamës së kërkimit: Filloni duke zgjedhur diapazonin e kërkimit nga pozicioni i parë left  në pozicionin e fundit right  të grupit.
  2. Gjeni pikën e mesit: Llogaritni pikën e mesit duke mesatarizuar left pozicionin dhe pozicionin e djathtë; kjo është pika e mesme e gamës së kërkimit.
  3. Krahasoni vlerat: Krahasoni vlerën në pikën e mesme me vlerën e synuar.
  4. Rezultati i krahasimit të trajtuar: Nëse vlera në pikën e mesme përputhet me vlerën e synuar, kthejeni këtë pozicion. Nëse vlera në pikën e mesme është më e vogël se vlera e synuar, përditësoni pozicionin e majtë në mes + 1 për të kërkuar gjysmën e djathtë. Nëse vlera në pikën e mesme është më e madhe se vlera e synuar, përditësoni pozicionin e djathtë në mes- 1 për të kërkuar gjysmën e majtë.
  5. Përsëriteni: Përsëritni hapat 2 deri në 4 derisa të gjendet vlera ose të mos ketë më elementë për të kontrolluar left > right.

Avantazhet dhe disavantazhet

Përparësitë:

  • Performanca efikase: Kompleksiteti kohor i algoritmit është O(log n), duke e bërë atë shumë efikas për trajtimin e grupeve të të dhënave të mëdha.
  • Efektive për grupe të dhënash të mëdha: Kërkimi binar është efektiv në reduktimin e numrit të elementeve që duhen ekzaminuar shpejt për grupe të mëdha të dhënash.

Disavantazhet:

  • I aplikueshëm vetëm për vargje të renditura: Algoritmi funksionon vetëm në vargje të renditura.
  • Numri i ndryshueshëm i hapave: Numri i hapave që kërkohen për të gjetur vlerën varet nga pozicioni i tij në grup dhe mund të marrë shumë hapa për vlerat afër skajeve.

Shembull: Kërkimi binar për gjetjen e vlerës 12 në një grup të renditur në 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.";  
}

Shpjegimi i Shembullit

  1. Fillojmë me diapazonin fillestar të kërkimit nga pozicioni i parë left = 0 deri në pozicionin e fundit right = 6  të grupit.
  2. Ne llogarisim pikën e mesme(mesa) duke mesatarizuar pozicionet majtas dhe djathtas; mid = 3. Vlera në mes është 12.
  3. Krahasojmë vlerën në mid(12) me vlerën e synuar(12) dhe gjejmë një përputhje, kështu që kthejmë pozicionin 3.
  4. Algoritmi përfundon dhe ne nxjerrim rezultatin "Vlera 12 e gjetur në pozicionin 3".