#include <ctime>
#include <iostream>
#include <stdio.h>
#include <sys/time.h>
#include <unistd.h>


using namespace std;


int Liniowo(int t[],int ile,int sz_liczba){

for(int i=1;i < ile;i++){
 if(sz_liczba == t[i]) {
 break;
 }

}

}

int Binarnie(int t[],int ile,int sz_liczba){

int k = sz_liczba;
int p = -1; 
int L = 0; 
int ik = ile - 1;
int ip = 0;
int isr;
  while(ip <= ik)
  {
    L++;
    isr = (ip + ik) >> 1;
    if(t[isr] == k)
    {
      p = isr; break;
    }
    else if(k < t[isr])
      ik = isr - 1;
    else
      ip = isr + 1;
  }

}


int main(){


//typ danych potrzebny do liczenia sekund. posiada pola tv_sec i tv_usec.
//pierwsze z nich przechowuje sekundy a drugie mikrosekundy( 10^(-6) sekundy )
struct timeval tv;
struct timeval tv2;
struct timezone tz;

int czas;
/*unsigned long long*/ int sz_liczba;
/*unsigned long long*/ int ile;

//ile elementow w tablicy:
cout << "Ile elementów w tablicy?" << endl;
cin >> ile;

//jakiej liczby szukac:
cout << "Podaj szukana liczbe: " << endl;
cin >> sz_liczba;
//deklarujemy tablice 'ile' elementów typu INT
int *t;
t = new int[ile];
for (int i=0; i < ile; i++) {
    t[i] = i;
}

//------------------------------------------------
//pobieramy bieżący czas (sekundy i mikrosekundy)
gettimeofday(&tv;, &tz;);
//wykonujemy funkcje Liniowo szukającą liczby najprostrzym sposobem:
Liniowo(t,ile,sz_liczba);
//pobieramy bieżący czas
gettimeofday(&tv2;, &tz;);
//------------------------------------------------
//liczymy czas jaki został wykorzystany na wykonanie (1)
czas = ((tv2.tv_sec*1000000)+tv2.tv_usec)-((tv.tv_sec*1000000)+tv.tv_usec);
//wypisujemy dane
cout << "Czas(algorytm liniowy): " << czas << "[usec]" << endl;
//------------------------------------------------
gettimeofday(&tv;, &tz;);
Binarnie(t,ile,sz_liczba);
gettimeofday(&tv2;, &tz;);
//------------------------------------------------
//liczymy czas jaki został wykorzystany na wykonanie (1)
czas = ((tv2.tv_sec*1000000)+tv2.tv_usec)-((tv.tv_sec*1000000)+tv.tv_usec);
//wypisujemy dane
cout << "Czas(algorytm połówkowy): " << czas << "[usec]" << endl;
}