//Wyszukiwanie binarne
//www.algorytm.org

#include<cstdio>
#include<conio.h>	// naglowek pozwalajacy uzyc funkcji getch()

int n,t[100],x,s,indeks;

int bin_search(int l, int p)
{
	if (l>p) return -1;	// jesli l jest na prawo od p (jest większe) to nasz przedział jest pusty czyli nie znajdziemy x-a
	s=(l+p)/2;	// srodek rozpatrywanego przedzialu to srednia arytm. poczatku i konca
	if (t[s]>x) return bin_search(l,s-1);	// pod s mamy za duza liczbe, wiec musimy szukac wczesniej (bardziej na lewo)
	if (t[s]<x) return bin_search(s+1,p);	// j.w. tyle ze odwrotnie - mamy za mala liczbe, szukajmy na prawo
	return s;
}

int main()
{
	// Wczytujemy dane
	printf("Podaj wielkosc tablicy.\n");
	scanf("%d", &n);
	printf("Teraz podaj %d liczb w kolejnosci rosnacej.\n", n);
	for (int i=0; i<n; i++)
		scanf("%d", &t[i]);
	printf("Podaj liczbe do znalezienia.\n");
	scanf("%d", &x);

	indeks=bin_search(0,n-1);	// szukamy w calej tablicy (czyli od indeksu 0 do ostatniego n-1)
	if (indeks==-1) printf("Nie ma takiej liczby.\n");	// program zwrocil (return) -1 jesli przedzial byl juz pusty
	else printf("%d ma indeks %d (indeksujemy od 0).\n", x, indeks);

	printf("Wcisniecie dowolnego klawisza zakonczy program.");
	getch();
	return 0;
}