close

Algorytm wyszukiwania binarnego (Binary Search) w PHP: wyjaśnienie, kroki i przykład

Algorytm wyszukiwania binarnego to wydajna metoda znajdowania określonej wartości w posortowanej tablicy. Takie podejście dzieli tablicę na mniejsze części i w sposób ciągły porównuje wartość w środkowej pozycji zakresu wyszukiwania z wartością docelową. Jeśli wartości są zgodne, zostanie znaleziona żądana wartość; w przeciwnym razie algorytm kontynuuje zawężanie zakresu wyszukiwania i powtarza proces, aż zostanie znaleziona wartość lub nie będzie już więcej elementów do zbadania.

Kroki:

  1. Zainicjuj zakres wyszukiwania: Rozpocznij od wybrania zakresu wyszukiwania od pierwszej left  do ostatniej pozycji right  tablicy.
  2. Znajdź punkt środkowy: Oblicz punkt środkowy, uśredniając left i właściwe pozycje; jest to środkowy punkt zakresu wyszukiwania.
  3. Porównaj wartości: porównaj wartość w punkcie środkowym z wartością docelową.
  4. Wynik porównania uchwytu: jeśli wartość w punkcie środkowym odpowiada wartości docelowej, zwróć tę pozycję. Jeśli wartość w punkcie środkowym jest mniejsza niż wartość docelowa, zaktualizuj lewą pozycję do środka + 1, aby przeszukać prawą połowę. Jeśli wartość w punkcie środkowym jest większa niż wartość docelowa, zaktualizuj prawą pozycję do środka- 1, aby przeszukać lewą połowę.
  5. Powtarzaj: powtarzaj kroki od 2 do 4, aż zostanie znaleziona wartość lub nie będzie więcej elementów do sprawdzenia left > right.

Zalety i wady

Zalety:

  • Wydajna wydajność: złożoność czasowa algorytmu wynosi O(log n), co czyni go wysoce wydajnym w przypadku obsługi dużych zbiorów danych.
  • Skuteczne w przypadku dużych zestawów danych: Wyszukiwanie binarne skutecznie zmniejsza liczbę elementów do szybkiego zbadania w przypadku dużych zestawów danych.

Niedogodności:

  • Dotyczy tylko posortowanych tablic: Algorytm działa tylko na posortowanych tablicach.
  • Zmienna liczba kroków: liczba kroków wymaganych do znalezienia wartości zależy od jej pozycji w tablicy, a dla wartości znajdujących się blisko końców może zająć wiele kroków.

Przykład: Wyszukiwanie binarne w celu znalezienia wartości 12 w posortowanej tablicy w 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.";  
}

Wyjaśnienie przykładu

  1. Zaczynamy od początkowego zakresu wyszukiwania od pierwszej left = 0 do ostatniej pozycji right = 6  tablicy.
  2. Punkt środkowy(środek) obliczamy poprzez uśrednienie lewej i prawej pozycji; mid = 3. Wartość w środku wynosi 12.
  3. Porównujemy wartość w mid(12) z wartością docelową(12) i znajdujemy dopasowanie, więc zwracamy pozycję 3.
  4. Algorytm kończy się i wyświetlamy wynik „Wartość 12 znaleziona na pozycji 3”.