// Binserach - wyszukiwanie (przez polowienie) elementu w posortowanej tablicy
// zlozonosc = log(n)

#include<stdio.h>
#include<conio.h>
const int n=12;
int tab[n]={1,2,6,18,20,23,29,32,34,39,40,41};
int x;

int szukaj(int tab[],int x)
{ enum {TAK,NIE} Znalazlem=NIE;
  int left=0,right=n-1,mid;
  
  while(left<=right && Znalazlem!=TAK)
   {  mid=(left+right)/2;
      if(tab[mid]==x) Znalazlem=TAK;
      else if(tab[mid]<x) left =mid+1;
           else           right=mid-1;
   }  
  if(Znalazlem==TAK) return mid; 
  else               return -1;
}

void main()
{ printf("Prosze podac wartosc x=");
  scanf("%d",&x);
  for(int i=0;i<n;i++) printf("%d,",tab[i]);
  if(szukaj(tab,x)!=-1)
    printf("\nElement %d znajduje sie na pozycji: %d",x, szukaj(tab,x));
  else 
    printf("\nElement %d nie nalezy do tablicy.", x);
  getch();  
}

/* 
   plus:

   Problem 1: Wyszukanie pierwszego (z lewej) "skoku" w posortowanej tablicy.
              skok = i z zakresu 0,..,n-1 takie, ze tab[i] != tab[i+1].

   Problem 2: Wyszukanie pierwszej (z prawej) "luki" w posortowanej tablicy.
              luka = i z zakresu 0,.., n-1 takie, ze tab[i]+1 < tab[i+1].
*/