Klasa II wyszukiwanie

Wyszukiwanie liniowe (ang. linear search), zwane również sekwencyjnym (ang. sequential search) polega na przeglądaniu kolejnych elementów tablicy T. Jeśli przeglądany element posiada odpowiednie własności (np. jest liczbą o poszukiwanej wartości), to zwracany jest jego indeks w tablicy i algorytm się kończy. W przeciwnym razie poszukiwania są kontynuowane aż do przejrzenia wszystkich pozostałych elementów. Jeśli poszukiwany element nie zostanie znaleziony, to jest zwracany indeks niemożliwy, np. -1.

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 T, n N
T	–	tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
p	–	indeks pierwszego elementu tablicy T, od którego rozpoczniemy poszukiwania. p C
k	–	poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z

Wyjście:

Indeks elementu tablicy T o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze

–

przebiega przez kolejne indeksy elementów T. i

Lista kroków:

K01:	Dla i = p,p+1,...,n-1: wykonuj K02	; przeglądamy kolejne elementy w tablicy
K02:	Jeśli T[i] = k, to zakończ z wynikiem i	; jeśli napotkamy poszukiwany element, zwracamy jego pozycję
K03:	Zakończ z wynikiem -1	; jeśli elementu nie ma w tablicy, zwracamy -1

Ćwiczenia

Napisać program, który wczyta do tablicy poniższy ciąg liczb (poprzez schowek i wklejanie). Pierwsza liczba określa ilość elementów do wczytania.

200
41 82 21 38 92 94 95 26 64 99 30 32 36 50 29 63 51 13 54 68
11 19 70 38 70 45 50 23 76 37 70 81 80 13 15 22 60 43 88 97
87 33 31 90 12 16 68 64 84 66 90 76 37 42 70 10 56 13 65 41
29 95 87 45 29 37 17 34 67 40 82 68 14 62 39 98 19 14 32 68
59 70 90 40 38 61 60 12 43 62 38 86 12 80 24 64 50 98 90 78
47 17 94 94 64 51 35 76 89 41 26 86 68 92 73 82 56 59 48 23
17 30 15 88 66 36 39 70 78 60 39 92 56 68 25 74 38 66 49 28
31 86 15 64 60 31 93 16 75 70 73 94 46 11 99 40 93 58 83 83
71 19 85 58 11 96 50 56 50 49 54 58 26 13 82 80 17 42 67 16
38 40 31 15 83 68 53 35 43 82 30 90 35 80 11 66 30 86 56 81

A następnie:

wyszuka w tablicy indeksy wszystkich liczb o wartości 11.
zliczy w tablicy wszystkie liczby o wartości 17.
zliczyć w tablicy wszystkie liczby parzyste.

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 T, n N
T	–	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 T

Wyjście:

pozycja elementu zbioru T o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze

–

przebiega przez kolejne indeksy elementów T. i

Numer	Operacja
1	i ← 0
2	Jeśli i ≥ n, to zakończ z wynikiem -1
3	Jeśli T[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 T[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	ⁿ/₂ + 1
3	Jeśli T[i] = k, to zakończ z wynikiem i	ⁿ/₂ + 1
4	i ← i + 1	ⁿ/₂
5	Idź do 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	T[n] ← k
1b	i ← 0
2	usunięta
3	Jeśli T[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 T 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	T[n] ← k	1
1b	i ← 0	1
2
3	Jeśli T[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	T[n] ← k	1
1b	i ← 0	1
2
3	Jeśli T[i] = k, to idź do 6	ⁿ/₂ + 1
4	i ← i + 1	ⁿ/₂
5	Idź do 3	ⁿ/₂
6	Jeśli i = n, to zakończ z wynikiem -1	1
7	Zakończ z wynikiem i	1
	RAZEM:	*³/₂n* + 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 T, n N
T	–	tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n. Ostatnia pozycja T[n] będzie zajęta przez wartownika, zatem nie może być używana do innych celów.
p	–	indeks pierwszego elementu T, od którego rozpoczniemy poszukiwania. p C
k	–	poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w T

Wyjście:

Pozycja elementu zbioru T o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze

–

przebiega przez kolejne indeksy elementów T. i

Lista kroków:

K01:	T[n] ← k	; na końcu zbioru umieszczamy wartownika
K02:	i ← p	; przeszukiwanie rozpoczynamy od pozycji p
K03:	Jeśli T[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 z wynikiem -1	; sprawdzamy, czy znaleziony element jest wartownikiem
K07:	Zakończ z wynikiem i	; jeśli nie, to zwracamy pozycję znalezionego elementu

Ćwiczenie:

Napisz program wykorzystujący algorytm wyszukiwania z wartownikiem, który wczyta do tablicy ciąg liczb, gdzie pierwsza liczba oznacza ilość pozostałych elementów

100
45 63 21 36 32 74 88 56 69 44
35 78 30 65 14 48 32 14 40 49
52 16 50 34 70 99 85 11 99 65
85 66 38 19 35 98 29 92 29 85
25 62 25 96 84 57 45 53 31 28
36 88 52 96 95 19 45 57 93 71
30 52 61 31 67 10 47 51 46 29
59 14 32 43 32 68 64 56 15 29
90 55 52 26 59 81 64 75 43 73
29 97 63 57 89 55 44 99 45 70

A następnie znajdzie w niej pierwsze wystąpienia liczb:

Informatyka dla klas II

Wyszukiwanie liniowe

Algorytm wyszukiwania liniowego/sekwencyjnego

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków:

Wejście

Wyjście:

Zmienne pomocnicze

Algorytm wyszukiwania liniowego z wartownikiem

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków: