#include<stdio.h>

//bilo kakav niz, sortiran ili nesortiran
int linearna_pretraga(int a[], int n, int x){
  int i;

  for(i=0; i<n; i++)
    if (a[i] == x)
      return i;

  return -1;
}

//iskljucivo primenljiva na sortiran niz
int binarna_pretraga(int a[], int n, int x){

  int levo, desno, sredina;
  levo = 0; 
  desno = n-1;

  while(levo<=desno){
    sredina = (levo+desno)/2;
    if (x < a[sredina])
      desno = sredina-1;
    else if (x > a[sredina])
      levo = sredina + 1;
    else 
      return sredina;
  }

  return -1;
}

main(){
  int niz1[] = {1,2,3,4,5};
  int niz2[] = {5,6,2,3,1};

  int n1, n2, k;

  n1 = sizeof(niz1)/sizeof(int);
  n2 = sizeof(niz2)/sizeof(int);

  printf("Unesite broj koji trazite:\n");
  scanf("%d", &k);

  //Binarna pretraga se primenjuje samo na sortirane nizove
  if (binarna_pretraga(niz1, n1, k) >= 0)
    printf("Broj %d se nalazi u prvom nizu!\n", k);
  else 
    printf("Broj %d se ne nalazi u prvom nizu!\n", k);

  //Linearna pretraga se moze primeniti na svaki niz
  if (linearna_pretraga(niz2, n2, k) >= 0)
    printf("Broj %d se nalazi u drugom nizu!\n", k);
  else 
    printf("Broj %d se ne nalazi u drugom nizu!\n", k);
}

/*
  int da_li_je_rastuci(int a[], int n);
 */