Metoda poszukiwań w tablicach posortowanych, która polega na podzieleniu tablicy na kilka bloków i wyszukaniu liniowym tylko w tym bloku, w którym docelowy element może się znajdować, w języku angielskim nosi nazwę

Wyjaśnienie

Metoda opisana w pytaniu to Jump Search, czyli algorytm wyszukiwania w posortowanych tablicach. Działa w następujący sposób:

1. Podział na bloki:

   • Tablica jest podzielona na bloki o tej samej długości (zazwyczaj pierwiastek kwadratowy z długości tablicy, czyli √n).

2. Przeskakiwanie między blokami:

   • Algorytm sprawdza elementy na końcach kolejnych bloków, aby znaleźć blok, w którym może znajdować się poszukiwany element.

3. Wyszukiwanie liniowe w bloku:

   • Po zidentyfikowaniu bloku, w którym może znajdować się szukany element, algorytm przechodzi do liniowego przeszukiwania tylko w obrębie tego bloku.

4. Złożoność czasowa:

   • W najgorszym przypadku złożoność czasowa wynosi O(sqrt{n}) , co czyni Jump Search wydajniejszym od liniowego przeszukiwania w przypadku dużych, posortowanych tablic.

Poprawna odpowiedź

D. Jump search.

Wyjaśnienie innych metod wyszukiwania

1. Exponential Search

   • Opis: Wyszukiwanie wykładnicze jest używane do znajdowania elementów w posortowanych tablicach. Najpierw algorytm sprawdza elementy w wykładniczo rosnących pozycjach (1, 2, 4, 8, ...), aż znajdzie zakres, w którym może być poszukiwany element. Następnie w tym zakresie stosuje Binary Search.
   • Złożoność czasowa: ( O(log n) .
   • Zastosowanie: Przydatne dla posortowanych tablic o dużych rozmiarach, zwłaszcza gdy rozmiar tablicy nie jest znany z góry.

2. Ternary Search

   • Opis: Wyszukiwanie trójdzielne dzieli tablicę na trzy części (zamiast dwóch, jak w wyszukiwaniu binarnym). Algorytm porównuje wartość z dwoma punktami podziału i wybiera jedną z trzech części, w której może znajdować się element, a następnie kontynuuje wyszukiwanie w tej części.
   • Złożoność czasowa: O(log_3 n) .
   • Zastosowanie: Stosowane głównie w przypadkach, gdy trzeba znaleźć maksimum lub minimum w funkcjach unimodalnych.

3. Binary Search

   • Opis: Wyszukiwanie binarne dzieli posortowaną tablicę na dwie części. Algorytm porównuje szukany element ze środkowym elementem tablicy. Jeśli szukany element jest mniejszy, wyszukiwanie kontynuuje się w lewej połowie, w przeciwnym razie w prawej.
   • Złożoność czasowa: O(log n).
   • Zastosowanie: Podstawowa i bardzo wydajna metoda wyszukiwania w posortowanych tablicach.

4. Jump Search

   • Opis: Opisany w poprzednim pytaniu. Działa przez podział tablicy na bloki, przeskakiwanie między blokami i liniowe wyszukiwanie w odpowiednim bloku.
   • Złożoność czasowa: O(sqrt{n}).
   • Zastosowanie: Skuteczny dla dużych, posortowanych tablic, jeśli dostęp do elementów tablicy nie jest zbyt kosztowny.

Podsumowanie

Każda z wymienionych metod jest stosowana w specyficznych sytuacjach:

• Exponential Search: Dla dużych, nieznanych rozmiarów tablic.
• Ternary Search: Gdy potrzebne jest przeszukiwanie trójdzielne.
• Binary Search: Najbardziej ogólna metoda dla posortowanych tablic.
• Jump Search: Przydatny, gdy dostęp do tablicy jest szybki, a tablica jest bardzo duża.