Zadanie 4a.
W posortowanej rosnąco tablicy $data znajdź pozycję (indeks) podanej liczby (np. 40) stosując wyszukiwanie binarne i funkcję iteracyjną. 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; // liczenie wykonań pętli
$licznik = 0;
while($l <= $p) {
$licznik++;
$sr = floor(($l + $p) / 2);
if($dane[$sr] == $szukana) return $sr; // zwracamy indeks elementu
if($dane[$sr] > $szukana) $p = $sr - 1; else $l = $sr + 1;
}
return -1; //zwracamy -1, gdy nie znajdziemy elementu
}
echo 'Liczba elementów w tablicy: ' . count($dane) . ")\n";
echo 'Szukam 40, indeks: ' . szukaj(0, count($dane) - 1, 40, $dane) . ', liczba wykonań pętli: ' . $licznik;
echo "\n";
echo 'Szukam 5, indeks: ' . szukaj(0, count($dane) - 1, 5, $dane) . ', liczba wykonań pętli: ' . $licznik;
Liczba elementów w tablicy: 16)
Szukam 40, indeks: 10, liczba wykonań pętli: 4
Szukam 5, indeks: -1, liczba wykonań pętli: 4Złożoność obliczeniowa algorytmu O(log n).