Wyszukiwanie liniowe z wartownikiem

Przedstawmy algorytm wyszukiwania liniowego w nieco inny sposób, który bardziej odpowiada jego realizacji w komputerze:

Dane wejściowe:

n - liczba elementów tablicy
T[] - tablica
v - poszukiwany element

Dane wyjściowe:

indeks elementu tablicy T[] zawierającego poszukiwany element v lub -1, jeśli elementu v nie znaleziono w tablicy.

Lista kroków:

K01: i ← 0
K02: Jeśli i ≥ n, to zakończ zwracając -1
K03: Jeśli T[i] = v, to zakończ zwracając i
K04: i ← i + 1
K05: Idź do K02

 

Zauważ, iż w każdym obiegu pętli przeszukującej algorytm wykonuje dwa porównania - w K02 oraz w K03. Pierwsze porównanie ma na celu sprawdzenie, czy indeks i wyszedł poza indeks ostatniego elementu w tablicy. Drugie porównanie sprawdza, czy element T[i] jest poszukiwanym elementem v. Otóż okazuje się, iż poprzez prostą modyfikację tablicy T[] możemy pozbyć się pierwszego porównania i w ten sposób przyspieszyć operację wyszukiwania. Zwróć uwagę, iż porównanie K02 staje się zbędne, jeśli poszukiwany element jest w zbiorze. Ma ono znaczenie tylko wtedy, gdy elementu v w zbiorze nie będzie.

Zatem wstawmy element v na koniec zbioru i usuńmy zbędne teraz porównanie K02. Musimy nieco zmodyfikować porównanie K03. Jeśli natrafimy na element v, to sprawdzamy w dalszej kolejności, czy leży on na pozycji mniejszej od n. Jeśli tak, to T[i] jest poszukiwanym elementem i kończymy zwracając jego pozycję. Jeśli pozycja elementu v wynosi n, to algorytm znalazł wstawiony przez nas element, zatem w zbiorze elementu v pierwotnie nie było - kończymy zwracając -1.

Wstawiony element nazywamy wartownikiem lub strażnikiem (ang. sentinel), a wyszukiwanie nosi nazwę wyszukiwania liniowego z wartownikiem (ang. sentinel linear search). Klasa złożoności algorytmu wciąż jest liniowa O(n), lecz wzrosła jego efektywność.

 

Algorytm wyszukiwania liniowego z wartownikiem

Dane wejściowe:

n - liczba elementów w tablicy
T[] - tablica n+1 elementowa
v - poszukiwany element

Dane wyjściowe:

indeks elementu tablicy T[] zawierającego poszukiwany element v lub -1, jeśli elementu v nie znaleziono w tablicy.

Lista kroków:

K01: T[n] ← v
K02: i ← 0
K03: Jeśli T[i] = v, to idź do K06
K04: ii + 1
K05: Idź do K03
K06: Jeśli i = n, to zakończ zwracając -1
K07: Zakończ zwracając i

Program:

Ćwiczenie na lekcji

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.