// Version 4: anyadimos busqueda binaria recursiva para comparar con iterativa

// g++ busquedas4.cpp -lrt -o busquedas4 -O3 && ./busquedas4 | tee busquedas4.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 busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
  if (inicio <= fin) {
    int medio = (inicio + fin) / 2;
    if (v[medio] < dato)
      return busquedaBinariaRecursiva(v, dato, medio + 1, fin);
    else if (v[medio] > dato)
      return busquedaBinariaRecursiva(v, dato, inicio, medio - 1);
    else
      return medio;
  }
  return -1;
}


int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
  return busquedaBinariaRecursiva(v, dato, 0, v.size() - 1);
}


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

  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;

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

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

}