Wyszukiwanie wartości z użyciem algorytmów wyszukiwania (wyszukiwanie binarne, interpolacyjne)

Założenie: Nauczyć się implementować wyszukiwanie binarne i interpolacyjne w PHP w celu efektywnego wyszukiwania elementów w posortowanych tablicach.

Krok po kroku:

1. Wyszukiwanie binarne: Algorytm wyszukiwania binarnego działa na posortowanych tablicach. Dzieli on tablicę na pół w każdej iteracji, eliminując połowę danych.

   Ten kod implementuje funkcję `binarySearch`, która przyjmuje posortowaną tablicę i wartość do znalezienia. Zwraca indeks elementu lub -1, jeśli element nie istnieje.

2. Wyszukiwanie interpolacyjne: Jest to ulepszenie wyszukiwania binarnego, które lepiej sprawdza się w tablicach o równomiernie rozłożonych wartościach. Zamiast dzielić tablicę na pół, szacuje pozycję elementu na podstawie jego wartości.

   
   = $arr[$low] && $x <= $arr[$high]) {
       $pos = $low + floor((($high - $low) / ($arr[$high] - $arr[$low])) * ($x - $arr[$low]));
       if ($arr[$pos] == $x) {
         return $pos;
       } elseif ($arr[$pos] < $x) {
         $low = $pos + 1;
       } else {
         $high = $pos - 1;
       }
     }
     return -1; // Element nie znaleziony
   }
   
   $arr = [2, 5, 7, 8, 11, 12];
   $x = 11;
   $result = interpolationSearch($arr, $x);
   if ($result == -1) {
     echo "Element nie znaleziony";
   } else {
     echo "Element znaleziony na pozycji: " . $result;
   }
   ?>
   				

   Podobnie jak w przypadku wyszukiwania binarnego, funkcja `interpolationSearch` zwraca indeks elementu lub -1, jeśli element nie istnieje.

Podsumowanie: Ten przykład pokazuje podstawy implementacji wyszukiwania binarnego i interpolacyjnego w PHP. Zachęcamy do dalszego zgłębiania tematu i eksperymentowania z różnymi algorytmami wyszukiwania.