Wyszukiwanie liniowe i z wartownikiem (Linear Search)

Zasada działania wyszukiwania liniowego

Wyszukiwanie liniowe (Linear Search / przeszukiwanie sekwencyjne) to najprostszy algorytm lokalizowania elementu w zbiorze danych. Przegląda tablicę element po elemencie, porównując każdy z nich z poszukiwaną wartością klucza.

Wyszukiwanie zwykłe vs z wartownikiem:

1. Wyszukiwanie liniowe klasyczne:
   • W każdej iteracji pętli wykonywane są dwa porównania: czy nie wyszliśmy poza zakres tablicy (i < n) oraz czy znaleźliśmy szukany element (tab[i] == szukany).
   • Złożoność czasowa: pesymistyczna O(n), średnia O(n), optymistyczna O(1).
2. Wyszukiwanie liniowe z wartownikiem (Sentinel Linear Search):
   • Na dodatkowej pozycji na samym końcu tablicy (tab[n] = szukany) umieszcza się tzw. wartownika (poszukiwaną wartość).
   • Dzięki temu element zawsze zostanie odnaleziony, co pozwala wyeliminować z pętli warunek sprawdzania granic tablicy (i < n). W każdej iteracji wykonuje się tylko jedno porównanie (tab[i] != szukany), co przyspiesza wykonanie pętli o ok. 20–30%.
   • Po wyjściu z pętli sprawdza się indeks: jeśli i < n, element istniał w tablicy pierwotnej; jeśli i == n, znaleziono jedynie wartownika (brak elementu).

// Wyszukiwanie z wartownikiem w C++:
int szukajZWartownikiem(int tab[], int n, int szukana) {
    tab[n] = szukana; // Ustawienie wartownika na końcu tablicy
    int i = 0;
    while (tab[i] != szukana) {
        i++;
    }
    return (i < n) ? i : -1; // -1 oznacza brak elementu w tablicy
}

Pułapki na egzaminie INF.04:

• Zaleta wartownika: Zmniejszenie liczby operacji porównań w pętli poprzez usunięcie sprawdzania warunku przekroczenia indeksu tablicy.
• Wyszukiwanie liniowe nie wymaga wcześniejszego posortowania tablicy (w przeciwieństwie do wyszukiwania binarnego).