Algorytmy wyszukiwania

Jak sama nazwa wskazuje, będziemy szukać. Będziemy szukać odpowiedniego elementu w n-elementowym zbiorze.
Pomożemy sobie takim przykładem. Mamy zbiór { 8 5 6 6 7 1 9 1 7 9 6 2 4 4 8 } i szukamy w nim elementu 2.

Prościej się nie da. Jedziemy cały zbiór od lewej do prawej i sprawdzamy czy element przy którym jesteśmy to ten właściwy. Czyli na naszym przkładzie; 8 - nie, 5 - też nie, 6 - nie, (...), 2 - o! znalezione!
Szukanego elementu może po prostu w zbiorze nie być, lub może być nawet na samym końcu. Złożoność czasowa jest prosta do policzenia.
Zakładając, że zbiór jest nieposortowany, prawdopodobieństwo znalezienie odpowiedniego elementu wynosi 1/n.
Pesymistyczna klasa złożoności czasowej: O(f) = n
Przykład kodu:

int[] zbior = {8,5,6,6,7,1,9,1,7,9,6,2,4,4,8};
int wielkosc_zbioru = 15;
int szukana = 2;

int zwroc_indeks_szukanej()
{
	for(int i=0; i<wielkosc_zbioru; i++)
		if(zbior[i] == szukana) return i;
	return -1;
}
					

Rodzaj wyszukiwania nie różni się niczym od sekwencyjnego. Diabeł tkwi natomiast w warunkach.
Zauważmy, że w wyszukiwaniu sekwencyjnym nie jesteśmy pewni, czy znajdziemy odpowiedni element zbioru. Możemy sobie pomóc i do naszego zbioru dostawić jeszcze jeden element. Szukamy 2, więc wstawmy taką wartość na koniec naszego zbioru. Nie musimy wtedy sprawdzać, czy nie skończyły się nam elementy wyszukiwania.
Klasa złożoności pozostaje taka sama, lecz oszczędzamy jedno porównanie na każdym elemencie zbioru.
Pesymistyczna klasa złożoności czasowej: O(f) = n
Przykład kodu:

int[] zbior = {8,5,6,6,7,1,9,1,7,9,6,2,4,4,8,2};
int miejsce_na_ktorym_dodalismy_wartownika = 16;
int wielkosc_zbioru = 15;
int szukana = 2;

int zwroc_indeks_szukanej()
{
	for(int i=0;; i++)
		if(zbior[i] == szukana){
			if(i == miejsce_na_ktorym_dodalismy_wartownika) return -1;
			return i;
		}
	return -1;
}
					

Jak w powyższym przykładzie, przelatujemy cały zbiór od lewej do prawej strony. Dla przykładu, poszukajmy sobie maksimum:
Weźmy pierwszy element ze zbioru jako wartośc startową. Nasze max wynosi teraz 8. Kolejno od lewej mamy 5, 8<5 więc ignorujemy i idziemy dalej, 6, 6, 7, 1, wszystko mniejsze, az dochodzimy do 9 która naturalnie jest większa od 8. Za nasze maksimum przyjmujemy więc liczbę 9 i kontynuujemy sprawdzanie, aż do końca zbioru. Otrzymany wynik: 9. Analogicznie sytuacja wygląda do sprawdzania minimum.
Pesymistyczna klasa złożoności czasowej: O(f) = n

Intuicyjnie, tak jak w powyższym przykładzie przelatywalibyśmy cały zbiór po kolei i sprawdzali czy kolejna liczba jest maksimum, badź minimum. Stosując metodę dziel i zwyciężaj możemy to zrobić w czasie o wiele krótszym. Metoda divide & conquer wymusza dzielenie problemu na mniejsze i znalezieniu głownego rozwiązania z rozwiązać mniejszych. Jak to zatem zrobić?
Bierzemy po dwa elementy ze zbioru i porównujemy je ze sobą. Element większy jest kandydatem na największą liczbę więc poddajemy go testowi na maksimum, analogicznie z elementem mniejszym, który przechodzi test na minimum.
Test polega na najprostszym sprawdzeniu czy dana liczba jest mniejsza/większa od aktualnie zapamiętanej jako minimum/maksimum.
Dla naszego przypadku bierzemy dwie pierwsze liczby, 8 i 5. 8 jest kandydatem na max, 5 na min. Jedziemy dalej, 6 i 6, są sobie równe więc robimy im test na max i min, nie przechodzą, więc w pamięci pozostają 8 i 5. Kolejna para to 7 i 1, 8 jest większe od 7 więc pozostaje na miejscu, natomiast 1 jest mniejsze od 3, więc w tej chwili nasze zapamiętane liczby to 8 i 1. Analogicznie postępując dostajemy w wyniku 9 i 1.
Pesymistyczna klasa złożoności czasowej: O(f) = n

Jeśli zbiór jest posortowany (np. rosnąco), to problem wyszukiwania elementu da się rozwiązać znacznie efektywniej stosując metodę zwaną wyszukiwaniem binarnym.
Jeśli zbiór jest pusty, to kończymy algorytm z wynikiem negatywnym. W przeciwnym razie wyznaczamy element leżący w środku zbioru. Porównujemy poszukiwany element z elementem środkowym. Jeśli są sobie równe, to zadanie wyszukania elementu jest wypełnione i kończymy algorytm. W przeciwnym razie element środkowy dzieli zbiór na dwie partycje - lewą z elementami mniejszymi od środkowego oraz prawą z elementami większymi. Jeśli porównywany element jest mniejszy od środkowego elementu zbioru, to za nowy zbiór poszukiwań przyjmujemy lewą partycję. W przeciwnym razie za nowy zbiór przyjmujemy prawą partycję. W obu przypadkach rozpoczynamy poszukiwania od początku, ale w nowo wyznaczonym zbiorze.

 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

 > > > > > > > 2 
 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

 > > > 2 
 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

   2 > 
 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

     2 
 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 

Każde porównanie sprowadza nam problem do zbioru o połowę mniejszego. W najgorszym przypadku wykonamy log₂n + 1 porównań. Zatem przedstawiony sposób wyszukiwania elementu zbioru posiada logarytmiczną klasę złożoności obliczeniowej O(log n). Czy to dużo, czy mało? Bardzo mało, logarytm rośnie wolno. Na przykład w zbiorze zawierającym 1.000.000.000 elementów algorytm wyszukiwania binarnego wykona maksymalnie 30 porównań, podczas gdy algorytm wyszukiwania liniowego będzie średnio musiał wykonać 500.000.000 porównań.
Pesymistyczna klasa złożoności czasowej: O(f) = log n

Na początek wypada podkreślić, że nadaje się ono tylko do zbiorów uporządkowanych liniowo. Jest to wyszukiwanie oparte na tej samej zasadzie co wyszukiwanie binarne. Różnica jest taka, że tam zbiór był zawsze dzielony na pół. Ale skoro nasze elementy mamy uporządkowane liniowo to szukana dwójka bedzie najprawdopodobniej gdzieś z lewej. Pozyskując wartośc pierwszego i ostatniego elementu ze zbioru możemy "na oko" wyliczyć sobie proporcje podziału i, jak wspomniałem przed chwilą, określić, że szukana 2 jest gdzieś z boku po lewej. W tym właśnie miejscu dzielimy nasz zbiór i postępujemy analogicznie do przykładu powyżej, dalej.
Pesymistyczna klasa złożoności czasowej: O(f) = log log n