// Version 1: solo busqueda secuencial, medicion imprecisa de momento

// Compilar: g++ busquedas1.cpp -lrt

#include <iostream>
#include <vector> 

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

using namespace std;

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(vector<int> v, int dato) { // Esto es malo! Lo veremos luego
  for (int i = 0; i < v.size(); i++)
    if (v[i] == dato)
      return i;
  return -1;
}


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

  cout << fixed << setprecision(10);

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

    // Creamos un vector aleatorio
    while (datosAleatorios.size() < talla)
      datosAleatorios.push_back(rand());

    // Buscamos siempre un dato que no está y medimos el tiempo de la búsqueda
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);

    busquedaSecuencial(datosAleatorios, -1);

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);

    cout << datosAleatorios.size() << "\t" << segundosDiferencia(tiempoInicial, tiempoFinal) << endl;

  }

}