Wyszukiwanie binarne

powrót

Algorytm szuka danego elementu w tablicy uporządkowanej (posortowanej). Złożoność obliczeniowa tego sposobu wyszukiwania jest rzędu $$O(log)$$. Oznacza to, że metoda jest znaczenie szybsza niż algorytm przeszukiwania liniowego. Dla tablicy $$1000-elementowej$$ wystarczy wykonać w pesymistycznej sytuacji około $$log_2\ 1000\ \approx 10$$ kroków, natomiast w przypadku przeszukiwania liniowego należy wykonać tych kroków $$1000$$.

Algorytm jest realizowany metodą "dziel i zwyciężaj". Dzieli on tablicę na mniejsze podtablice do momentu wyszukania pozycji (lub nie w przypadku gdy taki element nie istnieje) elementu szukanego.

Przeanalizujmy następujący zbiór 8 uporządkowanych liczb:

$$1\ 2\ 5\ 8\ 9\ 11\ 15\ 20$$

Potrzebne będą nam trzy zmienne pomocnicze:

$$l - $$ przechowuje numer lewego krańca tablicy,

$$r - $$ przechowuje numer prawego krańca tablicy,

$$sr - $$ przechowuje numer środkowego elementu tablicy.

W pierwszym kroku algorytmu ustawiamy:

int l = 0;
int p = 7;
int sr = (l+p)/2;

A więc mamy:

$$\overbrace{1}^{l =0} 2\ 5\ \overbrace{8}^{sr = 3}\ 9\ 11\ 15\ \overbrace{20}^{p = 7}$$

Następnie sprawdzamy czy szukany element znajduje się na pozycji $$sr$$. Jeśli tak to znaleźliśmy daną liczbę, w przeciwnym przypadku sprawdzamy czy szukana liczba jest mniejsza czy większa niż liczba znajdująca się na środkowej pozycji.

Jeśli jest mniejsza, tzn., że mamy do przeszukania lewą część badanej tablicy. Zmieniamy wartość zmiennej $$p$$:

$$p = sr - 1$$

a więc:

$$\overbrace{1}^{l=0}\ 2\ \overbrace{5}^{p=2}\ \overbrace{8}^{sr}\ 9\ 11\ 15\ 20$$.

W przypadku gdy jest większa to przeszukujemy prawą część tablicy. Zmieniamy wartość zmiennej $$l$$ na:

$$l = sr + 1$$

a więc:

$$1\ 2\ 5\ \overbrace{8}^{sr = 3}\ \overbrace{9}^{l = 4}\ 11\ 15\ \overbrace{20}^{p = 7}$$.

Czynność tą powtarzamy do momentu znalezienia szukanej wartości, lub gdy zmienne $$l$$ i $$r$$ spełnią warunek:

$$l > r$$

W takim przypadku element nie występuje w zbiorze liczb.

Algorytm można testować na stronie z automatyczną sprawdzarką tutaj.

Rozwiązanie iteracyjne:

//algorytm.edu.pl
#include<iostream>
using namespace std;

long long tab[1000000]; //tablica z posortowanymi elementami

//l - lewy index tablicy, p - prawy index tablicy
int szukaj(int l, int p, long szukana) 
{
	int sr;
	while(l<=p)
	{
		sr = (l + p)/2;
		
		if(tab[sr] == szukana)
			return sr;
			
		if(tab[sr] > szukana)
			p = sr - 1;
		else
			l = sr + 1;
}

	return -1; //zwracamy -1, gdy nie znajdziemy elementu
}

int main()
{
	long long n,szukana;
	
	cin>>n; //podajemy ilość elementów do wczytania n < 1000000
	
	for(int i=0;i<n;i++)
		cin>>tab[i]; //wczytanie elementów tablicy
		
	cin>>szukana;
 
	int pozycja = szukaj(0,n-1,szukana);
 
	if(pozycja==-1)
		cout<<"Liczba "<<szukana<<" nie występuje w zbiorze"<<endl;
	else
		cout<<"Liczba "<<szukana
<<" występuje w zbiorze w komórce o numerze "<<pozycja<<endl;
 
	return 0;
}

Rozwiązanie rekurencyjne:

//algorytm.edu.pl
#include<iostream>
using namespace std;

long long tab[1000000]; //tablica z posortowanymi elementami

//l - lewy index tablicy, p - prawy index tablicy
int szukaj(int l, int p, long szukana) 
{
     if(l>p)
       return -1;
       
	 int sr = (l+p)/2;
     
	 if(szukana == tab[sr])
	  	return sr;
    
    if(szukana < tab[sr])
        return szukaj(l,sr-1,szukana); //przeszukujemy lewą część tablicy
    else
        return szukaj(sr+1,p,szukana); //przeszukujemy prawą część tablicy
}

int main()
{
	long long n,szukana;
	
	cin>>n; //podajemy ilość elementów do wczytania n < 1000000
	
	for(int i=0;i<n;i++)
		cin>>tab[i]; //wczytanie elementów tablicy
		
	cin>>szukana;
 
	int pozycja = szukaj(0,n-1,szukana);
 
	if(pozycja==-1)
		cout<<"Liczba "<<szukana<<" nie występuje w zbiorze"<<endl;
	else
		cout<<"Liczba "<<szukana
<<" występuje w zbiorze w komórce o numerze "<<pozycja<<endl;
 
	return 0;
}