Wyszukiwanie liniowe

Wyszukiwanie liniowe (ang. linear search), zwane również sekwencyjnym (ang. sequential search) polega na przeglądaniu kolejnych elementów zbioru Z. Jeśli przeglądany element posiada odpowiednie własności (np. jest liczbą o poszukiwanej wartości), to zwracamy jego pozycję w zbiorze i kończymy. W przeciwnym razie kontynuujemy poszukiwania aż do przejrzenia wszystkich pozostałych elementów zbioru Z.

W przypadku pesymistycznym, gdy poszukiwanego elementu nie ma w zbiorze lub też znajduje się on na samym końcu zbioru, algorytm musi wykonać przynajmniej n  obiegów pętli sprawdzającej poszczególne elementy. Wynika z tego, iż pesymistyczna klasa złożoności obliczeniowej jest równa O(n), czyli jest liniowa – stąd pochodzi nazwa metody wyszukującej.

Często chcemy znaleźć wszystkie wystąpienia w zbiorze poszukiwanej wartości elementu. W takim przypadku algorytm na wejściu powinien otrzymywać dodatkowo pozycję (indeks) elementu, od którego ma rozpocząć wyszukiwanie. Pozycję tę przy kolejnym przeszukiwaniu podajemy zawsze o 1 większą od ostatnio znalezionej. Dzięki temu nowe poszukiwanie rozpocznie się tuż za poprzednio znalezionym elementem.

 

Algorytm wyszukiwania liniowego/sekwencyjnego

Wejście
n     liczba elementów w tablicy Z[ ], n  obrazek N
Z[ ]  – tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
p  – indeks pierwszego elementu Z[ ], od którego rozpoczniemy poszukiwania. p  obrazek C
k  – poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z[ ]
Wyjście:

Pozycja elementu zbioru Z[ ] o kluczu k  lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i  obrazek C
Lista kroków:
K01: Dla i  = p,p+1,...,n-1: wykonuj K02 ; przeglądamy kolejne elementy w zbiorze
K02:     Jeśli Z[i] = k, to zakończ zwracając i ; jeśli napotkamy poszukiwany element, zwracamy jego pozycję
K03: Zakończ zwracając -1 ; jeśli elementu nie ma w tablicy, zwracamy -1

 

Wyszukiwanie liniowe z wartownikiem

W algorytmie wyszukiwania liniowego sprawdzamy kolejne elementy zbioru aż do napotkania jego końca lub poszukiwanego elementu. Zachodzi pytanie, czy algorytm ten można przyspieszyć. Aby na nie odpowiedzieć, zapiszmy algorytm w poniższej postaci:

Wejście
n     liczba elementów w tablicy Z[ ], n  obrazek N
Z[ ]  – tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
k  – poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z[ ]
Wyjście:

pozycja elementu zbioru Z[ ] o kluczu k  lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i  obrazek C

 

Numer Operacja
1 i  ← 0
2 Jeśli i  ≥ n, to zakończ zwracając -1
3 Jeśli Z[i] = k, to zakończ zwracając i
4 i  ← i  + 1
5 Idź do 2

 

Sprawdzimy teraz ile operacji wykonuje ten algorytm w dwóch charakterystycznych przypadkach:

Przypadek pierwszy: poszukiwanej liczby nie ma w zbiorze. Poniżej przedstawiamy liczbę wykonań poszczególnych operacji w algorytmie:

 

Numer Operacja Liczba wykonań
1 i  ← 0 1
2 Jeśli i  ≥ n, to zakończ zwracając -1 n  + 1
3 Jeśli Z[i] = k, to zakończ zwracając i n
4 i  ← i  + 1 n
5 Idź do 2 n
  RAZEM: 4n  + 2

 

Przypadek drugi: poszukiwana liczba statystycznie znajduje się w środku zbioru – czasem znajdziemy ją wcześniej, a czasem później, zatem średnio będzie w środku.

 

Numer Operacja Liczba wykonań
1 i  ← 0 1
2 Jeśli i  ≥ n, to zakończ zwracając -1 n/2 + 1
3 Jeśli Z[i] = k, to zakończ zwracając i n/2 + 1
4 i  ← i  + 1 n/2
5 Idź do 2 n/2
  RAZEM: 2n  + 3

 

Zwróć uwagę, iż w każdym obiegu pętli nasz algorytm wykonuje dwa testy – w instrukcji numer 2 i 3. Usprawnienie pracy algorytmu będzie polegało na eliminacji testu 2. Jednakże test ten jest niezbędny, aby zakończyć przeglądanie tablicy w przypadku, gdy poszukiwanego elementu nie ma w zbiorze. Skoro tak, to wstawmy poszukiwany element na koniec zbioru, wtedy test 2 stanie się zbędny, nieprawdaż. Algorytm w zmienionej postaci wygląda następująco:

 

Numer Operacja
1a Z[n] ← k
1b i  ← 0
2 usunięta
3 Jeśli Z[i] = k, to idź do 6
4 i  ← i  + 1
5 Idź do 3
6 Jeśli i  = n, to zakończ zwracając -1
7 Zakończ zwracając i

 

Zmiany w stosunku do pierwotnego algorytmu są następujące:

1a – instrukcja umieszcza na końcu zbioru Z[ ] poszukiwany element o wartości k. Dzięki tej operacji dostajemy gwarancję, iż zawsze znajdziemy w zbiorze element k.

2 – test osiągnięcia końca zbioru stał się zbędny, ponieważ element o wartości k  zawsze znajdziemy w zbiorze.

3, 6, 7 – znalezienie elementu o wartości k  wymaga sprawdzenia, czy nie jest on elementem wstawionym do zbioru w operacji 1a. Jeśli tak, to zbiór faktycznie nie zawierał poszukiwanego elementu.

 

Przypadek pierwszy: poszukiwanej liczby nie ma w zbiorze. Poniżej przedstawiamy liczbę wykonań poszczególnych operacji w algorytmie:

 

Numer Operacja Liczba wykonań
1a Z[n] ← k 1
1b i  ← 0 1
2    
3 Jeśli Z[i] = k, to idź do 6 n  + 1
4 i  ← i  + 1 n
5 Idź do 3 n
6 Jeśli i  = n, to zakończ zwracając -1 1
7 Zakończ zwracając i 0
  RAZEM: 3n  + 4

 

Przypadek drugi: poszukiwana liczba statystycznie znajduje się w środku zbioru – czasem znajdziemy ją wcześniej, a czasem później, zatem statystycznie będzie w środku.

 

Numer Operacja Liczba wykonań
1a Z[n] ← k 1
1b i  ← 0 1
2    
3 Jeśli Z[i] = k, to idź do 6 n/2 + 1
4 i  ← i  + 1 n/2
5 Idź do 3 n/2
6 Jeśli i  = n, to zakończ zwracając -1 1
7 Zakończ zwracając i 1
  RAZEM: 3/2n  + 5

 

Porównajmy teraz wyniki z pierwszej i drugiej wersji algorytmu w poniższej tabelce (wartości ułamkowe z ostatniej kolumny należy rozumieć jako wartości statystyczne).:

 

n Przypadek pierwszy Przypadek drugi
Algorytm
podstawowy
Algorytm
usprawniony
Algorytm
podstawowy
Algorytm
usprawniony
4n + 2 3n + 4 2n + 3 3/2n + 5
1 6 7 5 6,5
2 10 10 7 8
3 14 13 9 9,5
4 18 16 11 11
5 22 19 13 12,5
6 26 22 15 14
... ... ... ... ...
10 42 34 23 20
100 402 304 203 155
1000 4002 3004 2003 1505
10000 40002 30004 20003 15005
... ... ... ... ...

 

Chociaż początkowo algorytm pierwszy wygrywa w ilości operacji, to przy wzroście liczby elementów zbioru widzimy wyraźnie, iż algorytm usprawniony wykonuje mniej operacji (począwszy od n > 3), zatem działa szybciej.

Opisana metoda wyszukiwania nosi nazwę wyszukiwania liniowego z wartownikiem (ang. Search with Sentinel). Wartownikiem jest dodany na końcu zbioru element równy poszukiwanemu. Dzięki niemu uzyskujemy zawsze pewność znalezienia poszukiwanego elementu w zbiorze. Jeśli jest to wartownik, to elementu poszukiwanego w zbiorze nie ma i zwracamy pozycję -1. Jeśli nie jest to wartownik, to znaleźliśmy poszukiwany element w zbiorze i zwracamy jego pozycję i.

Należy podkreślić, iż wyszukiwanie z wartownikiem można stosować tylko wtedy, gdy do zbioru da się dołączyć jeszcze jeden element.

 

Algorytm wyszukiwania liniowego z wartownikiem

Wejście
n      liczba elementów w tablicy Z[ ], n  obrazek N
Z[ ]  – tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n. Ostatnia pozycja Z[n] będzie zajęta przez wartownika, zatem nie może być używana do innych celów.
p  – indeks pierwszego elementu Z[ ], od którego rozpoczniemy poszukiwania. p  obrazek C
k  – poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z[ ]
Wyjście:

Pozycja elementu zbioru Z[ ] o kluczu k  lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i  obrazek C
Lista kroków:
K01: Z[n] ← k ; na końcu zbioru umieszczamy wartownika
K02: i  ← p ; przeszukiwanie rozpoczynamy od pozycji p
K03: Jeśli Z[i] = k, to idź do K06 ; sprawdzamy kolejne elementy zbioru
K04: i  ← i  + 1 ; jeśli element nie znaleziony, przechodzimy do następnego elementu w zbiorze
K05: Idź do K03  
K06: Jeśli i  = n, to zakończ zwracając -1 ; sprawdzamy, czy znaleziony element jest wartownikiem
K07: Zakończ zwracając i ; jeśli nie, to zwracamy pozycję znalezionego elementu

 


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

©2024 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe