Podręcznik

W różnych zastosowaniach informatycznych pojawia się konieczność wyszukania określonego elementu w zbiorze danych. Jest to problem, który występuje bardzo często oraz istnieje bardzo różnych metod poszukiwania danego elementu w zbiorze danych. W zależności od tego, czy dane są uporządkowane, oraz od oczekiwanej wydajności, można zastosować różne metody przeszukiwania. Dwiema najbardziej podstawowymi i jednocześnie powszechnie używanymi metodami są przeszukiwanie liniowe i przeszukiwanie binarne.

Przeszukiwanie liniowe (sekwencyjne) jest jedną z najprostszych metod znajdowania elementu w danym zbiorze. Polega ono na przeglądaniu elementów jeden po drugim, od początku do końca tablicy, aż do momentu odnalezienia poszukiwanej wartości lub zakończenia całego przeglądu. Metoda ta nie wymaga żadnego wcześniejszego uporządkowania danych i może być stosowana do dowolnych zbiorów – zarówno uporządkowanych, jak i nieuporządkowanych. Jego wadą jest jednak niska wydajność w przypadku dużych zbiorów, ponieważ w najgorszym przypadku konieczne jest sprawdzenie każdego elementu. Złożoność czasowa tej metody wynosi O. Algorytm ten możemy zrealizować przy pomocy bardzo prostego kodu aplikacji: 

#include <iostream>
#include <vector>
using namespace std;

int linearSearch(const vector<int>& T, int value) {
    for (int i = 0; i < T.size(); ++i) {
        if (T[i] == value) return i; // Zwracamy indeks znalezionego elementu
    }
    return -1; // Element nie został znaleziony
}

Znacznie szybszą metodą, ale działającą wyłącznie na zbiorach uporządkowanych, jest przeszukiwanie binarne. Nie przeszukuje ona danych sekwencyjnie lecz, wykorzystując fakt uporządkowania tablicy, dzieli ją na pół w każdym kroku. Na początku porównuje szukany element ze środkowym elementem tablicy. Jeśli jest mniejszy to poszukiwania kontynuowane są w lewej połowie, jeśli większy to w prawej. Proces ten jest powtarzany rekurencyjnie lub iteracyjnie, aż do odnalezienia szukanego elementu lub zawężenia obszaru poszukiwań do pustego przedziału. Przeszukiwanie binarne jest bardzo wydajne – jego złożoność czasowa wynosi O(log n) – ale, co istotne, wymaga wcześniejszego posortowania danych, co w pewnych sytuacjach może stanowić dodatkowy koszt. Poniżej przedstawiono przykładowy kod wyszukiwania binarnego:

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& T, int value) {
    int left = 0;
    int right = T.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (T[mid] == value) return mid;        // Zwracamy indeks
        else if (T[mid] < value) left = mid + 1;
        else right = mid - 1;
    }

    return -1; // Element nie został znaleziony
}

Dodatkowe informacje

Inną ciekawą metodą wyszukiwania elementów w zbiorze jest wykorzystanie algorytmów haszujących. Algorytmy haszujące (ang. hashing algorithms) to grupa technik umożliwiających szybkie odnajdywanie danych w zbiorach poprzez bezpośrednie obliczanie ich lokalizacji za pomocą funkcji haszującej. Zamiast przeszukiwać zbiór element po elemencie (jak w przeszukiwaniu liniowym) lub dzielić go na części (jak w przeszukiwaniu binarnym), algorytmy haszujące wyznaczają indeks tablicy, w którym dany element powinien się znajdować, a następnie sprawdzają tylko to miejsce. Podstawą działania tego typu algorytmów jest funkcja haszująca to specjalna funkcja matematyczna, która dla danego klucza (np. liczby, tekstu, obiektu) wylicza wartość całkowitą z określonego zakresu, odpowiadającą pozycji w tablicy. Jeśli dwa różne klucze dają ten sam wynik (co nazywa się kolizją), system musi je odpowiednio obsłużyć, np. przez zastosowanie listy jednokierunkowej w danym indeksie (tzw. łańcuchowanie) lub przez przeszukiwanie kolejnych komórek (ang. open addressing). Hashowanie jest bardzo efektywne w typowych zastosowaniach czas dostępu do elementu jest stały, czyli O(1). Dla porównania, przeszukiwanie binarne wymaga danych posortowanych i wykonuje O(log n) porównań.