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";;

 

}