close

Algoritm de căutare binar (Binary Search) în PHP: explicație, pași și exemplu

Algoritmul de căutare binară este o metodă eficientă de a găsi o anumită valoare într-o matrice sortată. Această abordare împarte matricea în părți mai mici și compară continuu valoarea din poziția de mijloc a intervalului de căutare cu valoarea țintă. Dacă valorile se potrivesc, se găsește valoarea dorită; în caz contrar, algoritmul continuă să restrângă intervalul de căutare și repetă procesul până când valoarea este găsită sau nu mai rămân elemente de examinat.

Pași:

  1. Inițializați intervalul de căutare: Începeți prin a selecta intervalul de căutare de la prima poziție left  la ultima poziție right  a matricei.
  2. Găsiți punctul de mijloc: Calculați punctul de mijloc făcând media left pozițiilor și dreapta; acesta este punctul de mijloc al intervalului de căutare.
  3. Comparați valori: comparați valoarea din punctul de mijloc cu valoarea țintă.
  4. Găsiți rezultatul comparației: dacă valoarea din punctul din mijloc se potrivește cu valoarea țintă, returnați această poziție. Dacă valoarea din punctul din mijloc este mai mică decât valoarea țintă, actualizați poziția din stânga la mijloc + 1 pentru a căuta jumătatea dreaptă. Dacă valoarea din punctul din mijloc este mai mare decât valoarea țintă, actualizați poziția din dreapta la mijloc- 1 pentru a căuta jumătatea din stânga.
  5. Repetați: repetați pașii de la 2 la 4 până când este găsită valoarea sau nu mai sunt elemente de verificat left > right.

Avantaje și dezavantaje

Avantaje:

  • Performanță eficientă: complexitatea în timp a algoritmului este O(log n), ceea ce îl face extrem de eficient pentru manipularea seturilor mari de date.
  • Eficient pentru seturi de date mari: Căutarea binară este eficientă în reducerea numărului de elemente de examinat rapid pentru seturi de date mari.

Dezavantaje:

  • Aplicabil numai matricelor sortate: algoritmul funcționează numai pe matrice sortate.
  • Număr variabil de pași: numărul de pași necesari pentru a găsi valoarea depinde de poziția acesteia în matrice și poate dura mulți pași pentru valorile din apropierea capetelor.

Exemplu: Căutare binară pentru găsirea valorii 12 într-o matrice sortată î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.";  
}

Explicația Exemplului

  1. Începem cu intervalul inițial de căutare de la prima poziție left = 0 până la ultima poziție right = 6  a matricei.
  2. Calculăm punctul de mijloc(mijloc) făcând media pozițiilor din stânga și din dreapta; mid = 3. Valoarea la mijloc este 12.
  3. Comparăm valoarea de la mid(12) cu valoarea țintă(12) și găsim o potrivire, așa că revenim la poziția 3.
  4. Algoritmul se termină și scoatem rezultatul „Valoarea 12 găsită la poziția 3”.