Wyszukiwanie wartości w tablicy z użyciem funkcji rekurencyjnej (wyszukiwanie binarne)

Założenie: Napiszemy funkcję rekurencyjną, która będzie wyszukiwała daną wartość w posortowanej tablicy za pomocą algorytmu wyszukiwania binarnego.

Krok po kroku:

1. Definicja funkcji rekurencyjnej: Funkcja przyjmuje posortowaną tablicę, wartość do wyszukania, indeks dolny i indeks górny zakresu wyszukiwania.

function binarySearchRecursive(array $arr, $value, $low, $high): ?int {
  if ($low > $high) {
    return null; // Wartość nie znaleziona
  }

  $mid = floor(($low + $high) / 2);

  if ($arr[$mid] == $value) {
    return $mid; // Wartość znaleziona
  } elseif ($arr[$mid] < $value) {
    return binarySearchRecursive($arr, $value, $mid + 1, $high); // Rekurencyjne wyszukiwanie w prawej połowie
  } else {
    return binarySearchRecursive($arr, $value, $low, $mid - 1); // Rekurencyjne wyszukiwanie w lewej połowie
  }
}
				

2. Przygotowanie posortowanej tablicy: Tworzymy przykładową posortowaną tablicę liczb.

$arr = [2, 5, 7, 8, 11, 12];
				

3. Wywołanie funkcji i wyświetlenie wyniku: Wywołujemy funkcję `binarySearchRecursive` i wyświetlamy indeks znalezionej wartości lub komunikat o braku wartości.

$valueToFind = 11;
$index = binarySearchRecursive($arr, $valueToFind, 0, count($arr) - 1);

if ($index !== null) {
  echo "Wartość $valueToFind znaleziona na indeksie: " . $index;
} else {
  echo "Wartość $valueToFind nie znaleziona w tablicy.";
}
				

Powyższy kod demonstruje prostą implementację wyszukiwania binarnego z użyciem rekurencji. Algorytm ten jest bardzo wydajny dla dużych, posortowanych zbiorów danych.

Ten przykład pokazuje podstawy rekurencji w PHP. Zachęcamy do eksperymentowania z różnymi wartościami i tablicami, aby lepiej zrozumieć działanie algorytmu wyszukiwania binarnego.