#include <cstdlib>
#include <time.h>
#include <iostream>
#include <string>

using namespace std;


int binarySearch(const int list[], int length,
const int& item)
{
    int first = 0;
    int last = length - 1;
    int mid;
    bool found = false;
    while (first <= last && !found)
    {
        mid = (first + last) / 2;
        if (list[mid] == item)
            found = true;
        else if (list[mid] > item)
            last = mid - 1;
        else
            first = mid + 1;
    }
    if (found)
        return mid;
    else
        return -1;
}
void loopTime(int array[],int sizeOfArray)
{//takes an array and its size as paramaters and loops it 10mill times
    clock_t timeStart; //and times the loop in seconds
    timeStart = clock();
    for(int i=0;i<1000000;i++)
    {
        binarySearch(array,sizeOfArray,2);
    }
    cout<<"Time "<<((((double)clock()-timeStart))/CLOCKS_PER_SEC)
            <<" in seconds of size "<<sizeOfArray<<endl;
}
void buildAndTestArray(const int SIZE)
{//builds an array and inputs it into loopTime()
    int arr[SIZE];
    for(int i=0;i<SIZE;i++)
    {
        arr[i]=0;
    }
    loopTime(arr,SIZE);
}
int main()
{

    const int size128=128;
    const int size512=512;
    const int size2048=2048;
    const int size8192=8192;
    const int size32768=32768;
    const int size131072=131072;
    const int size524288=524288;
    const int size2097152=2097152;
    buildAndTestArray(size128);
    buildAndTestArray(size512);
    buildAndTestArray(size2048);
    buildAndTestArray(size8192);
    buildAndTestArray(size32768);
    buildAndTestArray(size131072);
    buildAndTestArray(size524288);
    buildAndTestArray(size2097152);

    return 0;
}