Algorytmy

Zadanie 4a. W posortowanej rosnąco tablicy $data znajdź pozycję (indeks) podanej liczby (np. 40) stosując wyszukiwanie binarne i funkcję rekurencyjną. Jeśli szukana liczba nie znajduje się w tablicy, to należy zwócić liczbę -1.

$dane = Array
(
    [0] => 3
    [1] => 4
    [2] => 12
    [3] => 13
    [4] => 14
    [5] => 19
    [6] => 25
    [7] => 27
    [8] => 31
    [9] => 32
    [10] => 40
    [11] => 49
    [12] => 50
    [13] => 51
    [14] => 55
    [15] => 100
)

$licznik = 0;

function szukaj($l, $p, $szukana, $dane) {
  global $licznik;
  $licznik++;
  if($l > $p) return -1;
  $sr = floor(($l + $p) / 2);
  if($szukana == $dane[$sr]) return $sr;
  if($szukana < $dane[$sr])
    return szukaj($l, $sr - 1, $szukana, $dane); //przeszukujemy lewą część tablicy
  else
    return szukaj($sr + 1, $p, $szukana, $dane); //przeszukujemy prawą część tablicy
}

echo 'Liczba elementów w tablicy: ' . count($dane) . "\n";
echo 'Szukam 40, indeks: ' . szukaj(0, count($dane) - 1, 40, $dane) . ', liczba wywołań funkcji rekurencyjnej: ' . $licznik;
echo "\n";
echo 'Szukam 5, indeks: ' . szukaj(0, count($dane) - 1, 5, $dane) . ', liczba liczba wywołań funkcji rekurencyjnej: ' . $licznik;Liczba elementów w tablicy: 16
Szukam 40, indeks: 10, liczba wywołań funkcji rekurencyjnej: 4
Szukam 5, indeks: -1, liczba liczba wywołań funkcji rekurencyjnej: 9Złożoność obliczeniowa algorytmu O(log n).