Lut
20
2014
C // C++

Wyszukiwanie binarne – algorytm

Dzisiaj chciałbym zająć się tematyką wyszukiwania binarnego. To bardzo znana i efektywna metoda przeszukiwania zadanego ciągu.

Procedura działania:

Znajdujemy środkowy element tablicy, następnie dochodzi do porównania go z tym wyszukiwanym i wykonanie tego samego kroku dla odpowiedniej pozostałej części tablicy.

Zobaczmy jak działa to w naszym programie:

#include 
int szukaj(int tab[], int x, int prawy, int lewy)
{
int srodek=(prawy+lewy) / 2; // dzielimy tablice na połowę

if (tab[srodek]>x) //jesli tak, to element znajduje się być może w prawej części tablicy
{
	prawy=srodek;// indeks [srodek] przypisujemy prawemu elementowi
	szukaj(tab, x,prawy,lewy); //rekurencja
}

else if (tab[srodek]<x) //jesli tak, to element znajduje się być może w lewej części tablicy
{
	lewy=srodek; //indeks [srodek] przypisujemy lewemu elementowi
	szukaj(tab, x,prawy,lewy); //rekurencja
}

else 
return srodek; // element zostal znaleziony i zwracamy indeks znalezionego elementu
}

int main()
{

int tab[10]={0,5,9,11,21,43,52,94,110,129}; //inicjalizujemy przykladową tablice
int prawy=10; /inicjalizujemy liczbe elementow (prawy indeks)
int lewy=0; //inicjalizujem ylewy indeks
int x=129; //szukana liczba
printf("Szukany element znajduje sie = tab[%d]",szukaj(tab,x,prawy,lewy));

return 0;
}

Powiązane wpisy

Autor wpisu:

Jakub Kądzielawa - młodszy programista PHP, student Informatyki, który łączy pracę ze swoją pasją. Czasami narzeka na brak wolnego czasu.

1 komentarz+ Dodaj komentarz

  • Algorytm nie przewiduje sytuacji w której elementu nie znaleziono

Zostaw komentarz