Wyszukiwanie Wykładnicze

Algorytm

Wyszukiwanie Wykładnicze pozwala na bardzo szybkie wyszukiwanie poprzez wybranie elementów pomiędzy którymi możliwe jest znalezienie szukanego elementu. Do znalezienia indeksu wykorzystywany jest algorytm wyszukiwania binarnego. Algorytm wymaga, aby przeszukiwana lista była posortowana.

Opis

Na początek sprawdź czy pierwszy element nie jest element poszukiwanym. Jeśli jest to zwróć indeks 0, a jeśli nie to rozpocznij zawężanie przedziału. Na początku ustal i = 1. Dopóki element na pozycji 2ⁱ nie jest większy od szukanego elementu oraz licznik i jest mniejszy od długości listy n to podwajaj wartość i. Po ustaleniu zmiennej i wykonaj wyszukiwanie binarne na przedziale (i/2, i].

Przykład

Dana jest następująca tablica:

Poszukiwany jest element H. Początkowo należy sprawdzić pierwszy element listy (A). Jest on różny od H, więc rozpoczynamy poszukiwania od i = 1:

Element B występuje przed elementem H, więc podwajamy indeks tj. i = 2. Sprawdzamy element na wskazanym indeksie.

Element C ponownie występuje przed elementem H, więc podwajamy indeks. Teraz i = 4.

Element E ponownie występuje przed elementem H. Podwajamy indeks, więc i = 8.

Element I występuje po elemencie H. W tym momencie wiadomo, że element znajduje się na indeksie pomiędzy (i/2, i] czyli w tym przypadku (4, 8]. Oznacza to następujący obszar poszukiwań:

W tak ograniczonym obszarze należy wywołać wyszukiwanie binarne, które poda indeks szukanego elementu.

Złożoność

Po wstępnym przeszukiwaniu tablicy zagwarantowane jest to, że przeszukiwany obszar ma nie więcej jak n/2 elementów. Wynika to z faktu, że najgorszy możliwy przypadek jest wtedy, gdy szukany element znajduje się w ostatnim możliwym przedziale (n/2, n], więc ma on ma długość maksymalnie n/2. To poprawia wydajność wyszukiwania binarnego.

Implementacja

Algorytm wyszukiwania wykładniczego będzie korzystał z funkcji do wyszukiwania binarnego. Więcej informacji na jej temat oraz jej złożoność można znaleźć w artykule poświęconym wyszukiwaniu binarnemu.

Poniżej została przedstawiona przykładowa implementacja funkcji wyszukiwanieWykladnicze(), która dla podanej tablicy lista znajdzie element szukana.

1. int wyszukiwanieWykladnicze(double* lista, int n, double szukana) {
2.   if (lista[0] == szukana)
3.     return 0;
4.   int i = 1;
5.   while (i < n && lista[i] <= szukana)
6.     i = i * 2;
7.   return wyszukajBinarnie(lista, i / 2, min(i, n), szukana);
8. }

(2.) Sprawdź pierwszy element i jeśli jest on poszukiwany to (3.) zwróć indeks 0. W przeciwnym razie (4. - 6.) rozpocznij poszukiwanie przedziału możliwych indeksów. Po znalezieniu przedziału (7.) wywołaj wyszukiwanie binarne.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu, który wczyta od użytkownika listę, a wypisze na ekran indeks szukanego elementu. Należy pamiętać, że program nie sprawdza poprawności danych wejściowych.

1. int main() {
2.   int n;
3.   cout << "Podaj dlugosc tablicy:\n n = ";
4.   cin >> n;
5.   cout << "Podaj elementy:\n";
6.   double* L = new double[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> L[i];
9.   double szukana = 0;
10.   cout << "Podaj szukana wartosc:\n s = ";
11.   cin >> szukana;
12.   cout << wyszukiwanieWykladnicze(L, n, szukana) << endl;
13.   delete[] L;
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja