// Measure execution times of binary search and linear search
// on a sorted list.
//
// Usage:
//    ./<exec name> <size of list>

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[]) {
  
  // get the command line arguments
  if (argc < 2) { 
  	cout << "Usage: " << argv[0] << " <size> \n"; 
    exit(1);
  }
  int size = atoi(argv[1]);
  
  vector<int> v; 
  
  // fill the v vector with random integers and then sort
  for (int i = 0; i < size; i++) v.push_back(rand());
  
  sort(v.begin(), v.end());
  
  // initialize the random seed
  srand(time(NULL));
  
  int search_item;  
  double elapsed_secs;

  clock_t begin = clock();
  
  // do a 100k searches using binary search
  for (int i = 0; i < 100000; i++) {
    search_item = rand();
    binary_search(v.begin(), v.end(), search_item );
  }
    
  clock_t end = clock();

  
  elapsed_secs = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  cout << "\nBinary search: " << elapsed_secs << " seconds\n";
  
  begin = clock();
  
  // do 1000 searches using linear find. 
  for (int i = 0; i < 1000; i++) {
    search_item = rand();
    find(v.begin(), v.end(), search_item);
  }

  end = clock();

  elapsed_secs = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  cout << "Linear search: " << elapsed_secs << " seconds\n\n";
    
  return 0;
}