Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych Autor artykułu: mgr Jerzy Wałaszek |
©2014 mgr
Jerzy Wałaszek
|
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.
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 |
Indeks elementu tablicy T o kluczu k lub -1 w przypadku nie znalezienia elementu.
i | – | przebiega przez kolejne indeksy elementów T. i C |
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
A następnie:
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:
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 |
pozycja elementu zbioru T o kluczu k lub -1 w przypadku nie znalezienia elementu.
i | – | przebiega przez kolejne indeksy elementów T. i C |
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 | n/2 + 1 |
3 | Jeśli T[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 | 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 | 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.
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 |
Pozycja elementu zbioru T o kluczu k lub -1 w przypadku nie znalezienia elementu.
i | – | przebiega przez kolejne indeksy elementów T. i C |
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:
A następnie znajdzie w niej pierwsze wystąpienia liczb:
I Liceum Ogólnokształcące |
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