W zbiorze uporządkowanym elementy występują w określonej kolejności. Załóżmy, że szukamy elementu o wartości v. Wybieramy ze zbioru uporządkowanego element środkowy, oznaczmy go e_s. Jeśli v = e_s, to znaleźliśmy poszukiwany element i możemy zwrócić jego pozycję, kończąc wykonanie poszukiwania. Jeśli równość nie zachodzi, to musi zajść jedna z dwóch nierówności:

v < e_s - element poszukiwany może być tylko w pierwszej połówce.
v > e_s - element poszukiwany może być tylko w drugiej połówce.

Zatem po pierwszym teście ograniczamy liczbę elementów zbioru do połowy - pomijamy całą połówkę zbioru. Wybraną połówkę zbioru przyjmujemy za nowy zbiór i operację powtarzamy dotąd, aż znajdziemy poszukiwaną wartość, lub otrzymamy jako wynik zbiór pusty - elementu brak w zbiorze. Ponieważ przy każdym obiegu ilość elementów do przeszukania zmniejsza się o połowę, to taki algorytm, zwany wyszukiwaniem binarnym (ang. binary search), posiada klasę złożoności obliczeniowej O(log n). Jest ona bardzo korzystna. Przykładowo, algorytm liniowy w zbiorze 256 elementowym musiał wykonać 256 testów, aby stwierdzić, że poszukiwanego elementu brak. Tymczasem algorytm wyszukiwania binarnego dojdzie do tego samego wyniku już po 8 testach - czysty zysk.

Musimy uściślić sposób podziału zbioru na coraz mniejsze fragmenty. Zbiór odwzorowujemy w tablicy T[ ] składającej się z n elementów ponumerowanych kolejno od 0 do n-1. Określmy dwa indeksy:

i_p - indeks pierwszego elementu zbioru
i_k - indeks końcowego elementu zbioru

indeksy elementów tablicy T[ ]	0	1	2	...	n-2	n-1
indeksy początku i końca	*i_p*					*i_k*

Indeksy i_p i i_k określają obszar zbioru w tablicy T[ ]. Początkowo będą oczywiście równe: i_p = 0 oraz i_k = n - 1.

Na podstawie tych dwóch indeksów obliczamy indeks elementu środkowego i_s:

i_s=		i_p + i_k
		2

Jeśli zbiór jest uporządkowany rosnąco, to:

T[0]	T[1]	...	T[i_s-1]	T[i_s]	T[i_s+1]	...	T[n-2]	T[n-1]
i_p	←			i_s	→			i_k
elementy ≤ T[i_s]					elementy ≥ T[i_s]

Zatem w przypadku, gdy v < T[i_s], to przechodzimy do pierwszej połówki, w której indeksy przebiegają od i_p do i_s - 1. Element T[i_s] pomijamy, gdyż wiadomo, że o niego nam nie chodzi.

Jeśli v > T[i_s], to przechodzimy do drugiej połówki o indeksach od i_s + 1 do i_k. Pusty zbiór otrzymamy, gdy indeksy i_p oraz i_k miną się, tzn. i_p > i_k.

Algorytm wyszukiwania binarnego

Wejście

i_p	-	indeks pierwszego elementu w tablicy T[ ], i_p ∈C
i_k	-	indeks ostatniego elementu w tablicy T[ ], i_k ∈C
T[ ]	-	tablica do wyszukania elementu. Indeksy od i_p do i_k
v	-	wartość poszukiwanego elementu

Wyjście:

p = indeks elementu o wartości v
p = -1, jeśli nie odnalezienia elementu o wartości v

Zmienne pomocnicze

i_s

indeks elementu środkowego. i_s∈C

Lista kroków:

Krok 1:

p ← -1

; zakładamy, iż v nie występuje w zbiorze

Krok 2:

Jeśli i_p > i_k to zakończ

; w pętli poszukujemy elementu o wartości v

Krok 3:

i_s=		i_p + i_k
		2

; wyznaczamy element środkowy

Krok 4:

Jeśli v ≠ T[i_s], to idź do kroku 7

Krok 5:

p ← i_s

; element znaleziony, kończymy

Krok 6:

Zakończ

Krok 7:

Jeśli v < T[i_sr], to idź do kroku 10

; wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania

Krok 8:

i_p ← i_s + 1

; v > T[i_s] → druga połówka

Krok 9:

Idź do kroku 2

Krok 10:

i_k ← i_s - 1

; v < T[i_s] → pierwsza połówka

Krok 11:

Idź do kroku 2

Przykładowe dane dla programu:

Pierwsza liczba v określa poszukiwaną wartość. Druga liczba n określa ilość elementów w zbiorze. Następne n liczb definiuje n kolejnych elementów. Liczby zbioru są całkowite.

307
210
0 3 5 7 9 11 13 13 14 15 17 19 22 24 26
27 30 32 33 36 38 41 42 44 46 49 50 53 53 54
56 58 61 63 63 66 69 72 75 78 78 80 81 82 85
85 86 88 89 89 90 93 95 96 96 97 97 98 101 102
103 105 106 107 109 111 112 114 115 116 119 119 119 120 121
124 127 129 131 131 134 137 137 140 140 141 144 146 146 147
149 150 151 154 156 159 160 161 164 166 166 167 169 172 174
174 174 175 176 179 180 181 182 184 185 185 187 189 190 190
192 195 196 197 197 200 200 202 202 204 205 208 208 210 210
210 212 212 212 213 215 215 215 218 221 223 223 226 227 229
231 232 234 234 234 234 236 239 242 243 245 248 248 249 249
250 252 254 257 257 258 258 260 261 262 262 262 264 266 268
269 271 273 273 273 273 276 278 280 282 282 285 286 286 288
288 290 292 295 298 301 303 304 307 308 309 309 311 312 315

Wyszukiwanie interpolacyjne

Opisane w poprzednim rozdziale wyszukiwanie binarne (ang. binary search) zawsze szuka elementu o kluczu v w środku zbioru. Tymczasem, jeśli założymy liniowy rozkład wartości elementów w przeszukiwanym zbiorze, to możemy precyzyjniej wytypować spodziewaną pozycję poszukiwanego klucza na podstawie jego wartości. Wzór jest następujący:

– przeszukiwany zbiór

i_sr = i_p +		(v - T[i_p]) x (i_k - i_p)
		T[i_k] - T[i_p]

– poszukiwana wartość

i_p

– indeks pierwszego elementu partycji

i_k

– indeks końcowego elementu partycji

i_sr

– wyznaczona, przypuszczalna pozycja

Powyższy wzór wyprowadzamy z prostej proporcji. Jeśli zbiór posiada liniowy rozkład elementów, to odległość wartości poszukiwanej v od T[i_p] jest w przybliżeniu proporcjonalna do liczby elementów pomiędzy i_sr a i_p:

i_p

...

i_sr

...

i_k

T[i_p]

...

T[i_k]

Skoro tak, to zachodzi przybliżona proporcja:

i_sr - i_p	≈	v - T[i_p]	, mnożymy obustronnie przez i_k - i_p
i_k - i_p		T[i_k] - T[i_p]

i_sr - i_p ≈	(v - T[i_p]) x (i_k - i_p)	, dodajemy obustronnie i_p
	T[i_k] - T[i_p]

i_sr = i_p +		(v - T[i_p]) x (i_k - i_p)		, zaokrąglamy do wartości całkowitej i otrzymujemy wzór końcowy.
		T[i_k] - T[i_p]

Aby zrozumieć zaletę tego sposobu wyznaczania pozycji, przyjrzyjmy się poniższemu przykładowi, gdzie wyliczyliśmy pozycję wg wzoru z poprzedniego rozdziału oraz wg wzoru podanego powyżej. Poszukiwany element zaznaczono kolorem czarnym:

nr pozycji =	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
elementy T =	10	11	13	13	15	16	18	19	20	22	22	23	25	27	27	28	29	30	32
binarnie i_sr =										X
interpolacyjnie i_sr =					X

Binarne wyznaczenie pozycji:

i_sr =		i_p + i_k		=		0 + 18		=		18		= 9
		2				2				2

Interpolacyjne wyznaczenie pozycji:

i_sr = i_p +

(v - T[i_p]) x (i_k - i_p)

= 0 +

(15 - 10) x (18 - 0)

= 0 +

5 x 18

= 0 +

= 0 + 4 = 4

T[i_k] - T[i_p]

32 - 10

Metoda interpolacyjna wyznacza pozycję zwykle dużo bliżej poszukiwanego elementu niż metoda binarna (w przykładzie trafiamy za pierwszym razem). Zauważ, iż w metodzie binarnej nie korzystamy zupełnie z wartości elementów na krańcach dzielonej partycji, czyli działamy niejako na ślepo. Natomiast metoda interpolacyjna wyznacza położenie w zależności od wartości elementów zbioru oraz wartości poszukiwanego elementu. Działa zatem celowo dostosowując się do zastanych w zbiorze warunków. Stąd jej dużo większa efektywność.

Po wyznaczeniu położenia i_sr pozostała część algorytmu jest bardzo podobna do wyszukiwania binarnego. Sprawdzamy, czy element na pozycji i_sr posiada poszukiwany klucz v. Jeśli tak, to wyszukiwanie kończy się zwróceniem pozycji i_sr. W przeciwnym razie, jeśli v jest mniejsze od klucza elementu T[i_sr], to poszukiwania kontynuujemy w lewej części zbioru od elementu T[i_p] do T[i_sr - 1]. W przeciwnym razie szukamy w prawej części od T[i_sr + 1] do T[i_k]. Wyszukiwanie kończy się porażką, jeśli poszukiwany klucz wyjdzie poza przedział <T[i_p],T[i_k]>. W takim przypadku kończymy zwracając jako pozycję liczbę -1.

Wyszukiwanie interpolacyjne posiada klasę czasowej złożoności obliczeniowej równą O(log log n), zatem wyszukuje znacząco szybciej w zbiorach o liniowym rozkładzie elementów niż wyszukiwanie binarne o klasie O(log n).

Algorytm wyszukiwania interpolacyjnego

Wejście

i_p	–	indeks pierwszego elementu w tablicy T, i_p C
i_k	–	indeks ostatniego elementu w tablicy T, i_k C
T	–	tablica do wyszukania elementu. Indeksy od i_p do i_k
v	–	wartość poszukiwanego elementu – tzw. klucz

Wyjście:

p = indeks elementu o kluczu k lub
p = -1, jeśli nie odnalezienia elementu o takim kluczu.

Zmienne pomocnicze

i_sr

–

indeks elementu środkowego. i_sr

Lista kroków:

K01:

p ← -1

; zakładamy, iż k nie występuje w zbiorze

K02:

Dopóki T[i_p] ≤ v ≤ T[i_k] wykonuj K02...K07

; w pętli poszukujemy elementu o wartości v

K03:

i_sr ← i_p +		(v - T[i_p]) x (i_k - i_p)
		T[i_k] - T[i_p]

; wyznaczamy pozycję elementu interpolowanego

K04:

Jeśli v ≠ T[i_sr], to idź do K07

K05:

p ← i_sr

; element znaleziony, kończymy

K06:

Idź do K11

K07:

Jeśli v < T[i_sr], to idź do K10

; wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania

K08:

i_p ← i_sr + 1

; v > T[i_sr] → druga połówka

K09:

Następny obieg pętli K02

K10:

i_k ← i_sr - 1

; v < T[i_sr] → pierwsza połówka

K11:

Zakończ z wynikiem p

Wyszukiwanie dominanty zbioru

Problem wyszukiwania najczęstszej wartości (ang. searching for the most frequent value), czyli tzw. dominanty zbioru, możemy rozwiązać na kilka różnych sposobów. Pierwszym, najprostszym podejściem jest metoda bezpośrednia - naiwna:

Przeglądamy kolejne elementy zbioru i zliczamy liczbę wystąpień ich wartości w zbiorze. Można to robić tak - zapamiętujemy i-ty element i ustawiamy licznik jego wystąpień na 0. Następnie przeglądamy cały zbiór T, jeśli trafimy na element o takiej samej wartości, to licznik zwiększamy o 1. Po wykonaniu tej operacji porównujemy zawartość licznika z tymczasową maksymalną liczbą wystąpień (na początku algorytmu jest ona ustawiana na 0). Jeśli stan licznika jest większy, to zapamiętujemy go w tymczasowej maksymalnej liczbie wystąpień oraz zapamiętujemy wyszukiwaną wartość elementu. Gdy przeglądniemy w ten sposób i zliczymy wystąpienia wartości wszystkich elementów w zbiorze T, to otrzymamy element powtarzający się najczęściej oraz ilość tych powtórzeń.

Klasa złożoności obliczeniowej tak zdefiniowanego algorytmu jest równa O(n²). Jeśli elementów jest niewiele (do około 5000) i szybkość działania nie gra istotnej roli, to rozwiązanie naiwne jest do przyjęcia.

Algorytm znajdowania najczęstszej wartości - wersja 1

Wejście

n	–	liczba elementów w tablicy T, n ∈N
T	–	tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..

Wyjście:

mv – wartość najczęściej powtarzającego się elementu.
mc – liczba powtórzeń wartości mv w tablicy T.

Zmienne pomocnicze

i, j	–	przebiega przez kolejne indeksy elementów T. i,j ∈C
c	–	licznik wystąpień wartości elementu, c ∈C
v	–	wartość elementu, której liczbę wystąpień w T zliczamy.

Lista kroków:

K01:	mc ← 0	; zerujemy maksymalną liczbę wystąpień
K02:	Dla i = 0,1,...,n-1: wykonuj K03...K06	; przeglądanie rozpoczynamy od pierwszego elementu tablicy
K03:	v ← T[i]	; zapamiętujemy poszukiwaną wartość elementu
K04:	c ← 0	; zerujemy jej licznik wystąpień
K05:	Dla j = 0,1,..., n-1; wykonuj: Jeśli T[j] = v, to c ← c + 1	; zliczamy wystąpienia w
K06:	Jeśli c > mc, to mc ← c mv ← v	; sprawdzamy, czy w jest tymczasowo najczęstsze ; jeśli tak, zapamiętujemy liczbę wystąpień ; oraz wartość w
K07:	Zakończ

Przykładowe dane dla programu

Pierwsza liczba określa liczbę n elementów w zbiorze. Następne n liczb to elementy zbioru.

510
-463 -926 603 -901 826 879 376 -264 -189 10 -582 447 -664 547 702
453 -401 -398 10 -907 177 256 105 429 -63 995 -437 638 10 16
-16 320 40 141 -523 -284 138 405 17 -318 257 543 -651 -378 -278
9 27 -805 962 10 390 387 382 -210 32 -64 128 10 150 200
-4 12 32 530 -35 125 450 41 316 -301 -15 246 -849 -844 -165
27 -959 14 21 8 876 539 948 -662 5 13 32 254 577 888
-452 715 10 81 -725 359 361 381 -263 793 -144 -412 137 -119 -76
496 -189 467 149 -377 714 -273 443 490 -81 976 255 180 71 703
-620 161 978 -849 678 964 935 -188 602 -63 659 111 182 245 712
31 9 -8 603 178 -832 -743 -916 -341 87 65 -646 -707 830 612
-63 877 495 149 -290 2 698 166 -227 -400 -476 941 786 129 71
919 820 502 -28 481 943 815 -70 415 413 -484 1 329 250 78
915 -466 401 641 -802 543 10 -766 934 10 -786 10 951 768 886
231 762 74 -269 -508 10 134 -328 371 937 531 -756 470 -464 -488
-926 25 502 261 -339 115 67 -962 10 68 -882 863 -996 -791 924
742 -13 370 448 183 10 -147 41 -546 768 318 120 -522 466 628
756 968 58 358 -592 421 638 -978 980 988 444 -85 118 831 48
-858 -754 281 344 210 703 -84 -885 844 685 148 389 927 84 956
103 -310 -782 175 614 523 496 -897 10 399 924 -896 539 328 995
685 -336 548 961 15 175 982 -120 300 100 583 228 -588 672 950
-68 232 659 587 -909 967 218 -608 -838 779 343 -873 980 478 572
950 -944 395 754 10 994 26 -689 399 342 3 4 5 982 730
985 780 160 -816 933 628 433 -414 845 -646 322 450 716 849 619
-669 -855 278 173 687 471 304 460 377 -424 10 7 -20 130 721
883 654 47 145 224 771 927 10 579 38 361 773 661 -662 155
335 -9 159 283 -49 971 963 -318 913 431 811 266 -374 861 284
-232 672 564 -888 932 484 973 226 143 344 962 110 444 532 646
-16 3 29 14 83 -874 871 401 -381 473 -538 908 58 760 20
969 120 160 40 -584 -176 598 110 358 443 822 403 10 -46 199
-643 -614 574 5 8 13 4 -8 3 143 703 7 -242 50 61
34 487 526 290 818 219 968 710 -894 510 180 -447 708 -226 -296
-782 314 932 211 169 67 824 10 90 508 138 350 -824 799 882
-713 -212 335 -223 990 -735 502 743 -363 434 -484 10 -782 166 512
565 -654 934 364 397 168 4 5 6 603 524 183 303 10 399

Podany powyżej algorytm jest bardzo prymitywny i wykonuje wiele niepotrzebnych działań. Postarajmy się je wyeliminować.

Ze zbioru bierzemy KAŻDY element T[i] i zliczamy wystąpienia jego wartości dla CAŁEGO zbioru T. W ten sposób najczęstsza wartość mv zostanie zliczona mc² razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element w zbioru zliczamy tylko wtedy, gdy jest on różny od mv. Wynika z tego, iż na początku pracy algorytmu do mv musimy wpisać wartość różną od T[0] (dlaczego?).
Każdy element T[i] zliczamy w całym zbiorze. Tymczasem, jeśli wartość i-tego elementu wystąpiła wcześniej w zbiorze, to jest już zliczona. Jeśli nie wystąpiła wcześniej, to nie ma sensu jej tam szukać, nieprawdaż? W obu przypadkach wystarczy, jeśli zliczanie rozpoczniemy od pozycji i + 1 do końca zbioru. Elementy zliczone po prostu zliczymy ponownie, lecz w mniejszym zakresie. Elementy nowe zliczymy poprawnie, od miejsca ich pierwszego wystąpienia.
Jeśli w trakcie działania algorytmu w mc mamy chwilową maksymalną liczbę wystąpień pewnej wartości mv, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n - mc. Jeśli nowy element występuje na tej lub dalszej pozycji w zbiorze T, to liczba wystąpień jego wartości nie będzie już większa od mc, gdyż braknie takich elementów.

Oczywiście, powyższe ulepszenia nie zmienią klasy złożoności obliczeniowej – otrzymamy jedynie nieco szybszy algorytm klasy O(n²), który bardziej efektywnie rozwiązuje nasz problem.

Algorytm znajdowania najczęstszej wartości – wersja 2

Wejście

n	–	liczba elementów w tablicy T, n ∈N
T	–	tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..

Wyjście:

mv – wartość najczęściej powtarzającego się elementu.
mc – liczba powtórzeń wartości mv w tablicy T.

Zmienne pomocnicze

i, j	–	przebiega przez kolejne indeksy elementów T. i,j ∈C
c	–	licznik wystąpień wartości elementu, c ∈C
v	–	wartość elementu, której liczbę wystąpień w T zliczamy.

Lista kroków:

K01:	mc ← 0	; zerujemy maksymalną liczbę wystąpień
K02:	mv← T[0] - 1	; zapewniamy, iż mv zawiera wartość różną od T[0]
K03:	Dla i = 0,1,...,n-1: wykonuj K04...K08	; przeglądanie rozpoczynamy od pierwszego elementu tablicy
K04:	Jeśli T[i] = mv, to następny obieg pętli	; elementu najczęstszego nie zliczamy ponownie
K05:	v ← T[i]	; zapamiętujemy poszukiwaną wartość elementu
K06:	c ← 1	; ustawiamy jej licznik wystąpień
K07:	Dla j = i+1, i+2,..., n-1: wykonuj: Jeśli T[j] = v, to c ← c + 1	; zliczanie rozpoczynamy od pozycji następnej
K08:	Jeśli c > mc, to mc ← c mv ← v	; sprawdzamy, czy w jest tymczasowo najczęstsze ; jeśli tak, to zapamiętujemy liczbę wystąpień ; oraz najczęstszą wartość
K09:	Zakończ

Aby zmienić klasę złożoności z kwadratowej na liniową, musimy zmienić podejście do problemu. Postąpimy następująco:

Utworzymy tablicę liczników. Indeksy elementów tej tablicy będą odpowiadały wartością elementów ze zbioru. Całą tablicę liczników wyzerujemy. Następnie przeglądniemy zbiór i dla każdego napotkanego w nim elementu zwiększamy w tablicy liczników element o indeksie równym wartości tego elementu. Na koniec wyszukamy w tablicy liczników największy licznik, a wartość jego indeksu jest wartością najczęstszego elementu.

Algorytm ten się sprawdzi dla elementów całkowitych dodatnich. Jeśli elementy mogą również być ujemne, to należy przeliczać elementy zbioru T na odpowiednie indeksy tablicy liczników. W tym celu będziemy potrzebowali wartości minimalnej i maksymalnej z T, aby odpowiednio utworzyć tablicę liczników.

Tablica liczników ma rozmiar: Tmax - Tmin + 1

Element o wartości v ma indeks: v - Tmin

Indeks i odnosi się do elementu o wartości: i + Tmin.

Przykład:

Tablica T zawiera elementy od -3 do 6. Potrzebujemy 6 + 3 + 1 = 10 liczników dla elementów:

-3 -2 -1 0 1 2 3 4 5 6 → wartości elementów
0 1 2 3 4 5 6 7 8 9 → indeksy liczników

Algorytm znajdowania najczęstszej wartości – wersja 3

Wejście

n	–	liczba elementów w tablicy T, n ∈N
T	–	tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..

Wyjście:

mv – wartość najczęściej powtarzającego się elementu.
mc – liczba powtórzeń wartości mv w tablicy T.

Zmienne pomocnicze

Tmin	–	wartość minimalna w T
Tmax	–	wartość maksymalna w T
i	–	indeks. i ∈C
C	–	tablica liczników
m	–	ilość liczników

Lista kroków:

K01:	Wyszukaj w T wartości Tmin i Tmax
K02:	m ← Tmax - Tmin + 1	; wyznaczamy liczbę potrzebnych liczników
K03:	Utwórz tablicę C o rozmiarze m
K04:	Wyzeruj tablicę C
K05:	Dla i = 0,1,...,n-1: wykonuj C[T[i] - Tmin] ← C[T[i] - Tmin] + 1	; przeglądamy kolejne elementy zbioru i zwiększamy o 1 ; ich liczniki w tablicy C
K06:	mc ← C[0]
K07:	Dla i = 1,2,...,m-1: wykonuj Jeśli C[i] > mc, to mc ← C[i] mv ← i + Tmin	; wyszukujemy największy licznik
K08:	Usuń tablicę C
K09:	Zakończ

Tak zdefiniowany algorytm posiada klasę złożoności obliczeniowej O(n + m), gdzie n oznacza liczbę elementów, a m liczbę ich wartości. Zwróć jednakże uwagę, iż zysk na prędkości został okupiony większym zapotrzebowaniem na pamięć – tablica liczników rezerwuje dodatkowe m lokacji pamięci.

Wyszukiwanie k-tego największego elementu zbioru

Zadanie polega na wyszukaniu w tablicy T elementu v, od którego w tej tablicy jest dokładnie k - 1 elementów większych. Czyli element v jest k-tym największym elementem w tablicy T. Można zastosować następujący algorytm:

Przygotowujemy pustą tablicę M, w której będziemy składowali k największych elementów. Przeglądamy tablicę T i kolejne elementy próbujemy wstawić do M. Element z tablicy T trafia do M wtedy, gdy tablica M nie jest jeszcze zapełniona lub gdy element z T jest większy od pierwszego elementu M. Elementy wstawiamy, tak aby tablica M była uporządkowana nierosnąco. Gdy zakończymy przeglądanie tablicy T w pierwszym elemencie M będzie k-ty największy element z T.

Wyjaśnienia wymaga sposób działania na tablicy T. Będzie ona (k + 1) elementowa. Do wstawiania elementów wykorzystamy ideę wartownika. Tablicę M wypełnimy od M[0] do M[k-1] najmniejszą możliwą liczbą całkowitą – zagwarantuje to wstawianie najmniejszych elementu z T, jeśli w M jest jeszcze miejsce. Na ostatniej pozycji M[k] umieścimy największą liczbę całkowitą – zagwarantuje nam ona, iż wstawiane elementy nie wyjdą poza k-1 pozycję.

Algorytm wyszukiwania k-tego największego elementu

Wejście

n	–	liczba elementów w tablicy T, n > 0, n N
T	–	n-elementowa tablica, w której poszukujemy k-tej największej wartości
k	–	określa numer największej wartości, której szukamy w T, k > 0, k ≤ n, k N

Wyjście:

M[0] – k-ta największa wartość elementu w tablicy T. Dodatkowo M[0]...M[k-1] tworzy ciąg wartości maksymalnych z tablicy T

Elementy pomocnicze:

M	–	k + 1 elementowa tablica do przechowywania wartości maksymalnych z T
i,j	–	indeksy w tablicach T i M, i,j C
x	–	przechowuje element z T

Lista kroków:

K01:	Dla i = 0,1,...,k - 1, wykonuj M[i] ← najmniejsza liczba całkowita	; inicjujemy tablicę M
K02:	M[k] ← największa liczba całkowita	; wstawiamy górnego wartownika
K03:	Dla i = 0,1,...,n-1 wykonuj K04...K09	; przeglądamy kolejne elementy T
K04:	x ← T[i]	; zapamiętujemy i-ty element T
K05:	j ← -1	; indeks nieistniejącego elementu przed M[0]
K06:	Dopóki x > M[j+1] wykonuj K07...K08	; szukamy miejsca dla x w M
K07:	j ← j + 1	; przesuwamy się na następną pozycję w M
K08:	M[j] ← M[j+1]	; przesuwamy elementy, aby zrobić miejsce dla x
K09:	Jeśli j ≥ 0, to M[j] ← x	; jeśli trzeba, to wstawiamy element x do M
K10:	Zakończ zwracając M[0]	; w M[0] jest k-ty największy element

Przykładowe dane dla programu

Pierwsza liczba określa k. Druga liczba określa liczbę elementów n. Następne n liczb całkowitych jest zawartością zbioru.

12
510
-46 -267 632 -91 82 879 376 -264 -189 10 -582 447 -664 54 72
453 -401 -398 10 -97 177 256 105 429 -63 995 -437 638 10 16
-16 320 40 141 -523 -284 138 405 17 -318 257 543 -651 -378 -278
9 27 -805 962 10 39 387 382 -212 32 -64 128 10 150 20
-4 12 32 530 -35 125 450 41 316 -301 -15 246 -849 -844 -165
27 -959 14 21 8 876 539 948 -662 5 13 32 254 577 88
-452 715 10 81 -725 359 361 381 -263 793 -144 -412 137 -119 -76
496 -189 467 149 -377 714 -273 443 490 -81 976 255 180 71 703
-620 161 970 -849 68 964 935 -188 602 -63 659 111 182 245 712
31 9 -82 63 178 -832 -743 -916 -341 871 65 -646 -70 830 612
-63 877 495 14 -290 2 698 166 -227 -400 -476 941 786 129 715
99 820 502 -28 481 943 815 -70 415 413 -484 1 329 250 782
915 -466 401 641 -802 543 10 -766 934 10 -786 10 951 768 886
231 762 74 -269 -508 10 134 -328 371 937 531 -756 470 -464 -488
-926 25 502 261 -339 115 67 -962 10 68 -882 863 -996 -791 924
742 -13 370 448 183 10 -147 41 -546 768 318 120 -522 466 628
756 98 58 358 -592 421 638 -978 980 988 444 -85 118 831 48
-858 -754 281 344 210 703 -84 -885 844 685 148 389 927 84 956
103 -310 -782 175 614 523 496 -897 10 399 924 -86 539 328 995
685 -336 548 961 15 175 982 -120 300 100 583 228 -588 672 950
-68 232 659 587 -909 967 218 -608 -838 779 343 -873 980 478 572
90 -944 395 754 10 994 26 -689 399 342 3 4 5 982 730
985 780 160 -816 933 628 433 -414 845 -646 322 450 716 849 619
-669 -855 278 173 687 471 304 460 377 -424 10 733 -20 130 721
83 654 47 145 224 771 927 10 579 38 361 773 661 -662 155
35 -9 159 283 -49 971 963 -318 913 431 811 266 -374 861 284
-232 672 564 -888 932 484 973 226 143 344 962 11 444 532 646
-16 3 29 14 83 -874 871 401 -381 473 -538 908 58 760 20
96 120 160 40 -584 -176 598 110 358 443 822 403 310 -46 199
-643 -614 574 521 845 -136 43 -8 3 143 703 7 -242 50 615
34 487 526 290 818 219 968 71 -894 510 180 -447 708 -226 -296
-782 314 932 211 169 67 824 10 90 508 138 350 -824 799 882
-713 -212 335 -223 990 -735 502 743 -363 434 -484 10 -782 166 512
565 -654 934 364 397 168 43 555 65 603 524 183 303 10 399

Szybkie wyszukiwanie k-tego największego elementu

Jeśli nie musimy zachowywać oryginalnej kolejności elementów w zbiorze Z, to istnieje szybki algorytm znajdowania k-tego największego elementu, który posiada oczekiwaną klasę złożoności obliczeniowej równą O(n log n) (liniowo logarytmiczna). Algorytm ten nosi nazwę Szybkiego Wyszukiwania (ang. Quick Select) i został opracowany przez profesora Tony Hoare'a, twórcę jednego z najszybszych algorytmów sortujących – Sortowania Szybkiego (ang. Quick Sort).

Działanie algorytmu Szybkiego Wyszukiwania oparte jest na zasadzie Dziel i Zwyciężaj (ang. Divide and Conquer). Polega ona na rekurencyjnym podziale pierwotnego problemu na problemy prostsze tego samego typu. Podział wykonywany jest dotąd, aż rozwiązanie stanie się oczywiste. Następnie z rozwiązań podproblemów tworzymy rozwiązania na wyższych poziomach aż dojdziemy do rozwiązania problemu pierwotnego

W przypadku Szybkiego Wyszukiwania postępujemy w sposób następujący:

W zbiorze T wybieramy dowolny element. Oznaczmy go przez v i nazwijmy elementem zwrotnym (ang. pivot). Następnie dokonujemy podziału zbioru T na dwa podzbiory T_L i T_P (lewy i prawy). W podzbiorze T_P powinny znaleźć się elementy o wartościach nie większych od v. Z kolei w podzbiorze T_P powinny być elementy o wartościach nie mniejszych od v. Sam element v musi być pierwszym elementem podzbioru T_P. Po takim podziale sprawdzamy, czy v jest (n - k)-tym elementem zbioru T. Jeśli tak, to v jest k-tym największym elementem w tym zbiorze. Jeśli nie, to za nowy zbiór do podziału przyjmujemy ten z podzbiorów T_L lub T_P, w którym występuje pozycja (n - k)-ta i całą procedurę powtarzamy aż do znalezienia k-tego największego elementu.

Tworzenie partycji

Do utworzenia partycji musimy z tablicy wybrać jeden z elementów, który nazwiemy piwotem. W lewej partycji znajdą się wszystkie elementy niewiększe od piwotu, a w prawej partycji umieścimy wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdej z partycji nie jest ustalony.

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy:

piwot ← T[(lewy + prawy) div 2]

piwot	– element podziałowy
T[ ]	– dzielona tablica
lewy	– indeks pierwszego elementu
prawy	– indeks ostatniego elementu

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku tablicy – i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze.

Przykład:

Dla przykładu podzielimy na partycje zbiór:

{ 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 }

Lp.	Operacja	Opis
1.	7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3	Wyznaczamy na piwot element środkowy.
2.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5	Piwot wymieniamy z ostatnim elementem zbioru
3.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Na początku zbioru ustawiamy dwa wskaźniki. Wskaźnik i będzie przeglądał zbiór do przedostatniej pozycji. Wskaźnik j zapamiętuje miejsce wstawiania elementów mniejszych od piwotu
4.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wskaźnikiem i szukamy elementu mniejszego od piwotu
5.	2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Znaleziony element wymieniamy z elementem na pozycji j-tej. Po wymianie wskaźnik przesuwamy o 1 pozycję.
6.	2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
7.	2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
8.	2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
9.	2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
10.	2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
11.	2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
12.	2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
13.	2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
14.	2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
15.	2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
16.	2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 i j	Szukamy
17.	2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
18.	2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 i j	Szukamy
19.	2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 i j	Wymieniamy i przesuwamy j.
20.	2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 ^ i Lewa partycja j Prawa partycja	Brak dalszych elementów do wymiany. Piwot wymieniamy z elementem na pozycji j-tej. Podział na partycje zakończony.

Po zakończeniu podziału na partycje wskaźnik j wyznacza pozycję piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciąga się od początku zbioru do pozycji j - 1. Prawa partycja zawiera elementy większe lub równe piwotowi i rozciąga się od pozycji j + 1 do końca zbioru. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej – O(n).

Specyfikacja problemu

podziel(T, lewy, prawy)

Dane wejściowe

T[ ]	– Tablica zawierająca elementy do posortowania.
lewy	– indeks pierwszego elementu w tablicy, lewy C
prawy	– indeks ostatniego elementu w tablicy, prawy C

Dane wyjściowe

T[ ]	– Tablica podzielona na dwie partycje
j	– miejsce podziału

Zmienne pomocnicze

piwot	–	element podziałowy
i, j	–	indeksy, i, j C

Lista kroków

K01:

i ← [	lewy + prawy	]
	2

; wyznaczamy środek partycji

K02:

piwot ← T[i]

; zapamiętujemy piwot

K03:

T[i] ← T[prawy]

; na miejscu piwota umieszczamy prawy element partycji

K04:

j ← lewy

; indeks podziałowy umieszczamy na początku partycji

K05:

Dla i = lewy, lewy+1, ..., prawy-1: wykonuj:
    Jeśli T[i] < piwot to:
        T[i] ↔ T[j]
        j ← j + 1

; przeglądamy kolejne elementy partycji od pierwszego do przedostatniego

; elementy mniejsze od piwota wymieniamy z pozycją j-tą, po czym pozycję
; j-tą zwiększamy o 1

K06:

T[prawy] ← T[j]

; robimy miejsce na piwot

K07:

T[j] ← piwot

; wstawiamy piwot do tablicy

K08:

Zakończ zwracając j

Wyszukiwanie szybkie

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście

n	-	liczba elementów w zbiorze T
T[ ]	-	tablica n-elementowa odwzorowująca zbiór T, w którym poszukujemy k-tego największego elementu.
k	-	określa numer porządkowy największego elementu do znalezienia w T, k > 0, k N

Wyjście:

Wartość k-tego największego elementu zbioru T.

Zmienne pomocnicze:

i_p	-	indeks początku partycji, i_p C
i_k	-	indeks końca partycji, i_k C
p	-	zawiera pozycję elementu zwrotnego

podziel(T ,i_p,i_k) - funkcja dzieląca na dwie partycje.

Lista kroków:

K01:	i_p ← 0	; startowa partycja obejmuje cały zbiór T
K02:	i_k← n - 1
K03:	p ← podziel(T[ ], i_p, i_k)	; dokonujemy podziału na dwie partycje T_L i T_P
K04:	Jeśli p = n - k, to idź do K07	; sprawdzamy, czy znaleźliśmy poszukiwany element
K05:	Jeśli p > n - k to i_k ← p - 1 inaczej i_p ← p + 1	; jeśli nie, to w zależności od pozycji elementu zwrotnego ; szukamy w odpowiedniej partycji
K06:	Idź do K03
K07:	Pisz T[p]	; wyprowadzamy znaleziony element
K08:	Zakończ

Wyszukiwanie mediany zbioru

Medianą zbioru T nazwiemy wartość v, od której w tym zbiorze jest tyle samo elementów większych lub równych co mniejszych lub równych. Mediana posiada wiele ważnych zastosowań praktycznych w statystyce, grafice, obróbce dźwięku i wielu innych dziedzinach.

Jeśli zbiór T jest posortowany rosnąco, to

przy nieparzystej liczbie elementów n > 1 mediana jest elementem środkowym T[ⁿ/₂] (indeksy elementów rozpoczynają się od 0).
Na przykład dla zbioru T = {1,3,5,8,9} medianą jest element 5 - poprzedzają go dwa elementy 1 i 3 oraz wyprzedzają dwa elementy 8 i 9.
przy parzystej liczbie elementów n > 1 mediana jest średnią arytmetyczną dwóch środkowych elementów T[ⁿ/₂-1] i T[ⁿ/₂].
Na przykład dla zbioru T = {1,3,5,8,9,9} mediana jest równa (5 + 8) / 2 = 6,5. Od tej wartości jest dokładnie tyle samo elementów mniejszych (1,3,5) co większych (8,9,9).
Istnieją również pojęcia dolnej mediany (ang. lower median) i górnej mediany (upper median), które w tym przypadku oznaczają odpowiednio element T[ⁿ/₂-1] i T[ⁿ/₂] w ciągu uporządkowanym o parzystej liczbie elementów.

Medianę możemy w prosty sposób znaleźć wykorzystując nasz algorytm szybkiego wyszukiwania k-tego największego elementu. Twoim zadaniem jest napisanie odpowiedniego programu.

Informatyka dla klas III - Wyszukiwanie

Wyszukiwanie binarne

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków:

Wyszukiwanie interpolacyjne

Algorytm wyszukiwania interpolacyjnego

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków:

Wyszukiwanie dominanty zbioru

Algorytm znajdowania najczęstszej wartości - wersja 1

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków:

Przykładowe dane dla programu

Algorytm znajdowania najczęstszej wartości – wersja 2

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków:

Algorytm znajdowania najczęstszej wartości – wersja 3

Wejście

Wyjście:

Zmienne pomocnicze

Lista kroków:

Wyszukiwanie k-tego największego elementu zbioru

Algorytm wyszukiwania k-tego największego elementu

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków:

Szybkie wyszukiwanie k-tego największego elementu

Tworzenie partycji

Specyfikacja problemu

podziel(T, lewy, prawy)

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Wyszukiwanie szybkie

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Wyszukiwanie mediany zbioru