Blog programisty o C/C++ i PHP

Pobierz artykuł jako plik PDF

Wstęp

Wyszukiwanie określonej informacji w jakimś zbiorze jest niezwykle często wykonywaną czynnością w programowaniu. Może ono przybierać zarówno postać jawnych wywołań metod czy funkcji wyszukujących np.:

int index = szukaj(tablica, element);
vector::iterator it = find(kontener.begin(), kontener.end(), 10);

lub wywołań niejawnych, w których uruchamiamy mechanizm wykorzystujący wyszukiwanie np.:

int ileZmienionych = zamien(tablica, element, nowyElement);
urodziny["Rafał Żurawski"] = "01-10-1976";

Zastosowań jest wiele, ale jedno z nich wyjątkowo często używa mechanizmu wyszukiwania. Mowa tu o mapach.

Czym są mapy?

Mapa to taka specjalna tablica, fachowo określana jako tablica asocjacyjna. Hehe, a co to znów za dziwoląg? Myślę, że pojęcie tablicy nie jest Ci obce. Ku woli szybkiego przypomnienia powiem, że tablica to nic innego jak zbiór elementów. Każdy element ma ściśle określoną pozycję często nazywaną indeksem. Dzięki indeksowi mamy możliwość pobrania dowolnego, istniejącego w zbiorze elementu. Nie rzadkim udogodnieniem zbiorów jest możliwość natychmiastowego podawania jego liczebności bez konieczności iterowania po nim. Takim przykładem mogą być łańcuchy (zbiory, których elementami są znaki) w języku Pascal. Łańcuchy w językach C i C++ (NTS – ang. null terminated string) niestety wymagają przejrzenia wszystkich znaków aż do wystąpienia znaku końca łańcucha ‘’ (NULL) i ich zliczenia w celu określenia długości np.:

int t[10];
int a = t[4];

Położeniu w tablicy (indeksowi) przypisana jest dokładnie jedna informacja. Tablica zawsze wymaga rezerwacji ściśle określonej ilości miejsca w pamięci.

No dobrze, a co w takim razie oznacza słowo asocjacyjna?

Zauważ, że wspomniane tablice przechowują kolejne elementy od 1 .. N (N – ilość elementów). Jeśli zatem w takiej tablicy 1..10 chcielibyśmy przechować element, któremu przypisalibyśmy indeks większy niż 10 to jest to nie wykonalne, bo tablica taka ma maksymalnie 10 indeksów. W takiej sytuacji przychodzą nam z pomocą tablice asocjacyjne. Za ich pomocą można przechowywać informację w postaci (index |=> informacja) dla dowolnego indeksu. Mówimy, ze nastąpiła asocjacja (przyporządkowanie) informacji do indeksu. Nie musimy więc pamiętać 999 elementów aby móc przechować element o numerze 1000. np.:

map<string, string> urodziny;
urodziny["Rafał Żurawski"] = "01-10-1976";

Podczas każdej próby odczytu lub zapisu do takiej tablicy (mapy) następuje najpierw ustalenie gdzie fizycznie w pamięci znajduje się podany indeks, a dopiero potem wykonywane są operacje na danych skojarzonych z tym indeksem. W takiej sytuacji wyszukiwanie musi odbyć się jak najszybciej, bo jest bardzo często wykonywana operacją.

No to do dzielenia!

Najlepszą do tego celu metodą jest metoda wyszukiwania binarnego czyli inaczej „dziel i rządź”. W przeciwieństwie do algorytmu przeszukiwania całego zbioru element po elemencie , który daje w najgorszym przypadku N iteracji, omawiana metoda daje maksymalnie LOG2(N) + 1 iteracji. Wymaga ona jednak aby zbiór danych był posortowany.

Jak to działa?

Mamy daną tablicę TAB i jego dane są posortowane rosnąco czyli TAB[i] < TAB[i+1] jest zawsze spełniony.

[1]. Rozpoczynamy od wyznaczenia granic (początku i końca) poszukiwania – wartowników. Wartownicy to takie indeksy, które leżą tuż poza zbiorem. Jeśli nasz zbiór rozciąga się od 0 .. 99 to wartownikami są odpowiednio -1 i 100. UWAGA! umówmy się, że z nie będziemy działać na elementach określonych przez wartowników.

[2]. znajdujemy numer elementu środkowego za pomocą średniej arytmetycznej (bierzemy część całkowitą bez zaokrąglania) => (-1 + 100) / 2 = 49

[3]. sprawdzamy czy element środkowy (w tym przypadku TAB[49]) odpowiada poszukiwanej przez nas wartości. Jeśli TAK to KONIEC znaleźliśmy element. Jeśli NIE to idź do pkt. 4.

[4]. Ponieważ zbiór jest posortowany rosnąco możemy określić, po której stronie od elementu środkowego znajduje się szukany element. Jeśli jest on większy niż wartość elementu środkowego w naszym przypadku TAB[49] to znaczy że szukana wartość może znaleźć się na pozycjach pomiędzy 50..99. W związku z tym ustalamy modyfikujemy wartownika początkowego z wartości -1 na wartość 49. Jeśli element szukany jest mniejszy niż aktualny element środkowy (TAB[49]) to modyfikujemy z kolei wartownika końcowego z wartości 100 na 49.

[5]. Jeśli zakres poszukiwania nie zmniejszył się do zera (czyli różnica między wartownikami pozostaje > 1) to powtórz wszystko od punktu 2. Zwróć przy tym uwagę, że kolejne przebiegi operują na coraz węższych zakresach (2x mniejszych niż w przebiegu poprzedzającym). To właśnie z powodu podziału na dwie w przybliżeniu równe części algorytm nazywa się binarnym.

/* wejscie:
	tab - wskaznik na tablice elementow typu long
	n - liczba elementow w tablicy
	x - szukany element
    wyjscie:
	pozycja szukanego elementu lub -1 (gdy elementu nie ma w tablicy)
*/
int szukajBinarnie(long* tab, int n, long x)
{
	int startWart = -1; // wartownik poczatku
	int stopWart = n;  // wartownik konca
	int s;               // srodek przedziału

	while (stopWart - startWart > 1)
	{
		s = (startWart + stopWart) / 2;

		if (tab[s] == x)
			return(s);
		else if (tab[s] < x)
			startWart = s;
		else
			stopWart = s;
	}

	return(-1);
}