Przykładowy program realizujący algorytm wyszukiwania binarnego. W programie losowanych jest 100 liczb z zakresu 1-1000. Następnie dane są sortowane rosnąco. Dla posortowanych danych program sprawdza, czy wystąpiła liczba 100.
Na wyjściu otrzymujemy posortowane dane, wartości "x" i "y" dla kolejnych przebiegów pętli oraz wartość elementu środkowego. Jeżeli element środkowy jest poszukiwaną liczbą pętla kończy pracę, w przeciwnym wypadku sprawdzamy, w którą stronę przesunąć przeszukiwany zakres (zminiejszamy go poprzez przesunięcie "x" lub "y")
-
#include<iostream>
-
#include<ctime>
-
#include<cstdlib>
-
#include<algorithm>
-
-
using namespace std;
-
-
int T[100];
-
-
main()
-
{
-
srand(time(NULL));
-
-
//generujemy liczby <1-1000>
-
for (int i=0 ; i<100 ; i++)
-
T[i]= rand()%1000+1;
-
-
//sortujemy dane
-
sort(T,T+100);
-
-
//wypisujemy posortowana tablice
-
for (int i=0 ; i<100 ; i++)
-
cout<<T[i]<<", ";
-
-
//zmienna istnieje ustawiamy na FALSZ
-
bool istnieje=false;
-
-
//ustawiamy indexy x i y na poczatek i koniec przeszukiwanego zbioru
-
int x=0,y=99;
-
-
//ustalamy wyszukiwana wartosc s=100
-
int s=100;
-
-
//sprawdzamy czy wyszukiwana wartosc jest na poczatku lub na koncu zakresu
-
if (T[x]==s || T[y]==s) istnieje=true;
-
-
//jezeli nie, to wyszukujemy binarnie
-
while (y-x>1 && !istnieje)
-
{
-
//linia pomocnicza - wyswietlenie biezacych danych
-
cout << "\nx=" << x << "\ty="<< y << "\tT[(y+x)/2]=" << T[(y+x)/2];
-
-
//jezeli na srodku zakresu jest wyszukiwana liczba istnieje=true
-
if (T[(y+x)/2]==s)
-
istnieje=true;
-
else
-
//w przeciwnym razie modyfikujemy x lub y w zaleznosci od "za duzo lub za malo"
-
if (T[(y+x)/2]>s)
-
y=(y+x)/2;
-
else
-
x=(y+x)/2;
-
}
-
-
//wypisujemy wynik
-
if (istnieje) cout<<"\n\nTAK"; else cout<<"\n\nNIE";;
-
-
}
