Przeszukiwanie ciągu liczbowego z wartownikiem

Problem

W n-elementowym zbiorze Z wyszukać element posiadający pożądane własności.

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 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 C

Numer	Operacja
1	i ← 0
2	Jeśli i ≥ n, to zakończ z wynikiem -1
3	Jeśli Z[i] = k, to zakończ z wynikiem 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 z wynikiem -1	n + 1
3	Jeśli Z[i] = k, to zakończ z wynikiem 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 z wynikiem -1	n/2 + 1
3	Jeśli Z[i] = k, to zakończ z wynikiem 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 z wynikiem -1
7	Zakończ z wynikiem 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 z wynikiem -1	1
7	Zakończ z wynikiem 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 z wynikiem -1	1
7	Zakończ z wynikiem 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.