Wyszukiwanie liniowe

Przypomnijmy sobie najważniejsze informacje dotyczące algorytmu wyszukiwania liniowego.

Polega on na sprawdzaniu, czy kolejne elementy zbioru są szukaną liczbą. Możemy wyróżnić najprostszą wersję algorytmu oraz jego modyfikację – algorytm wyszukiwania liniowego z wartownikiem.

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów w tablicy tablica

• tablica – n-elementowa tablica liczb naturalnych

• szukana – liczba naturalna

Wynik:

• komunikat wskazujący indeks, pod którym znajduje się szukana liczba lub informujący, że w tablicy nie ma szukanej liczby

Wyszukiwanie liniowe bez wartownika

Zapiszmy nagłówek funkcji. Przyjmuje ona trzy argumenty – tablicę liczb, szukany element oraz liczbę elementów tablicy.

Na początku przypisujemy dwóm zmiennym pomocniczym odpowiednie wartości. Zmiennej znaleziono przypisujemy wartość fałsz, a zmiennej i wartość 0.

W kolejnym kroku zapisujemy pętlę dopóki. Będzie się ona wykonywać tak długo, jak długo będą spełnione dwa warunki – zmienna znaleziono będzie przechowywać wartość logiczną fałsz oraz wartość zmiennej i będzie mniejsza od długości tablicy, czyli wartości zmiennej n.

W pętli zapisujemy warunek logiczny jeżeli. Będziemy sprawdzać, czy wartość i-tego elementu tablicy jest równa szukanej liczbie  – jeżeli tak, wypiszemy odpowiedni komunikat, przypiszemy zmiennej znaleziono wartość prawda i zakończymy działanie algorytmu; jeżeli nie, zwiększymy wartość zmiennej i o 1.

W sytuacji, gdy po wyjściu z pętli dopóki wartością zmiennej znaleziono będzie fałsz, wypiszemy komunikat, że szukana liczba nie została znaleziona.

funkcja wyszukiwanie_liniowe(tablica, szukana, n)
    znaleziono ← fałsz
    i ← 0
    dopóki znaleziono != prawda oraz i < n wykonuj:
        jeżeli tablica[i] = szukana
            wypisz "Znaleziono liczbę na pozycji " + i
            znaleziono ← prawda
            zakończ działanie pętli
        i ← i + 1

    jeśli znaleziono = fałsz
        wypisz "Nie znaleziono szukanej liczby"

Operacjami, które najbardziej wpływają na złożoność tego algorytmu, są operacje porównania (wykonujące się w pętli dopóki). Dla n liczb może się ich wykonać, zależnie od ułożenia danych, od 1 do n, ponieważ w najgorszym wypadku musimy sprawdzić wszystkie liczby. Zatem złożoność czasowa tego algorytmu to $O\left(n\right)$.

Wyszukiwanie liniowe z wartownikiem

Wartownika dodajemy na początku lub na końcu tablicy. Zależnie od implementacji może to być zarówno liczba, która nie występuje w tablicy, jak i wartość szukana.

Przedstawimy wersję, w której wartownik jest szukaną liczbą. Umieścimy go na końcu tablicy.

Zapiszmy nagłówek funkcji. Ponownie przyjmuje ona trzy argumenty – tablicę liczb, szukany element oraz liczbę elementów tablicy.

Na początku umieszczamy wartownika na końcu tablicy, a zmiennej pomocniczej i przypisujemy wartość 0.

W kolejnym kroku zapisujemy pętlę dopóki. Będzie się wykonywać tak długo, jak długo wartość i-tego elementu tablicy będzie różna od szukanej liczby.

W każdej iteracji pętli będziemy zwiększać wartość zmiennej pomocniczej o 1.

Zapisujemy warunek logiczny jeżeli. Będziemy sprawdzać, czy wartość zmiennej i jest mniejsza od różnicy długości tablicy oraz liczby 1. Jeśli tak, wypiszemy odpowiedni komunikat mówiący o tym, że szukana liczba została znaleziona pod indeksem równym i. W przeciwnym wypadku wypiszemy komunikat mówiący o tym, że szukana liczba nie została znaleziona.

funkcja wyszukiwanie_liniowe_wartownik(tablica, szukana, n)
    tablica[n] ← szukana
    i ← 0

    dopóki tablica[i] != szukana wykonuj:
        i ← i + 1

    jeśli i < n - 1:
        wypisz "Znaleziono liczbę na pozycji " + i
    w przeciwnym przypadku:
        wypisz "Nie znaleziono szukanej liczby"

Ponownie operacjami, które najbardziej wpływają na złożoność tego algorytmu, są operacje porównania (wykonujące się w pętli dopóki). Może się ich wykonać, zależnie od ułożenia danych, od 1 do n. Zatem złożoność czasowa tego algorytmu to również $O\left(n\right)$. Zwróćmy jednak uwagę na to, że poprzez dodanie wartownika wyeliminowaliśmy konieczność sprawdzania przy każdym kolejnym elemencie, czy nie przekroczyliśmy rozmiaru tablicy – zredukowaliśmy zatem liczbę instrukcji.