// Version 3: cambiamos paso por valor por paso por referencia para ver como cambian los resultados

// g++ busquedas3.cpp -lrt -o busquedas3 -O3 && ./busquedas3 | tee busquedas3.resultados

#include <iostream>
#include <vector> 

#include <iomanip> // setprecision
#include <cstdlib> // rand
#include <ctime>   // clock_gettime

#include <algorithm> // sort

using namespace std;

#define SEGUNDOS_ITERACIONES 5

double segundosDiferencia(timespec inicio, timespec fin) {
  const double nano = 1e9;
  return ( (fin.tv_sec + fin.tv_nsec / nano) - (inicio.tv_sec + inicio.tv_nsec / nano) );
}


int busquedaSecuencial(const vector<int> & v, int dato) {
  for (int i = 0; i < v.size(); i++)
    if (v[i] == dato)
      return i;
  return -1;
}


int busquedaBinariaIterativa(const vector<int> & v, int dato) {
  int inicio = 0, fin = v.size() - 1;
  while(inicio <= fin) {
    int medio = (inicio + fin) / 2;
    if (v[medio] < dato)
      inicio = medio + 1;
    else if (v[medio] > dato)
      fin = medio - 1;
    else
      return medio;
  }
  return -1;
}


int main () {
  vector<int> datosAleatorios;
  timespec tiempoInicial, tiempoFinal;
  int iteraciones, posicion1, posicion2;

  cout << fixed << setprecision(10);

  for (int talla = 2; talla <= 1e8; talla *= 2) {

    // Creamos un vector aleatorio ordenado

    while (datosAleatorios.size() < talla)
      datosAleatorios.push_back(rand());
    sort(datosAleatorios.begin(), datosAleatorios.end());

    // Buscamos siempre un dato que no esta y medimos el tiempo de la busqueda

    iteraciones = 0;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);
    do {
      posicion1 = busquedaSecuencial(datosAleatorios, -1);
      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);
      iteraciones++;
    } while(tiempoFinal.tv_sec - tiempoInicial.tv_sec < SEGUNDOS_ITERACIONES);
    double tiempoBusquedaSecuencial = segundosDiferencia(tiempoInicial, tiempoFinal) / iteraciones;

    iteraciones = 0;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);
    do {
      posicion2 = busquedaBinariaIterativa(datosAleatorios, -1);
      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);
      iteraciones++;
    } while(tiempoFinal.tv_sec - tiempoInicial.tv_sec < SEGUNDOS_ITERACIONES);
    double tiempoBusquedaBinariaIterativa = segundosDiferencia(tiempoInicial, tiempoFinal) / iteraciones;

    if (posicion1 != -1 || posicion2 != -1)
      cout << "ERROR" << endl;
    else
      cout << datosAleatorios.size() << "\t" << tiempoBusquedaSecuencial << "\t" << tiempoBusquedaBinariaIterativa << endl;


  }

}