Algoritmi lezione 22 - ricerca binaria

#include <iostream>
#include <fstream>

#include <chrono>

using namespace std;

const int MAX_PAROLE = 500000;
const int MAX_CERCATE = 10000;

string vocabolario[MAX_PAROLE];
string da_cercare[MAX_CERCATE];

enum Stato {START, STOP};
auto Cronometro(Stato stato = Stato::START)
{
  static std::chrono::time_point<std::chrono::system_clock> inizio;
  static std::chrono::time_point<std::chrono::system_clock> fine;

  if (stato == Stato::START)
  {
    inizio = chrono::high_resolution_clock::now();
    fine = inizio;
  }
  else
    fine = chrono::high_resolution_clock::now();


  return chrono::duration_cast<std::chrono::milliseconds>(fine - inizio).count();
}

int leggi_file(string path_file, string v[], int capienza_vettore)
{
 //per leggere useremo un I-nput F-ile STREAM = IFSTREAM
  ifstream leggi(path_file); //il cosiddetto file handle (riferimento al file su disco)

  //test per successo apertura
  if (!leggi)
    throw runtime_error("File non trovato\n");

  //lettura una intera riga alla volta
  string riga="";

  //getline restituisce false quando le righe sono finite
  int conta_righe = 0;
  while ( getline(leggi, riga) )
  {
    if (conta_righe>=capienza_vettore)
      throw runtime_error("Capienza vettore insufficiente\n");

    v[conta_righe] = riga;
    conta_righe++;
  }

  leggi.close(); leggi.clear();

  return conta_righe;

}

int partiziona(string v[], int inizio, int fine)
{
    string pivot = v[inizio];

    int cont = 0;
    for (int i = inizio + 1; i <= fine; i++) {
        if (v[i] <= pivot)
            cont++;
    }

    //mettiamo il pivot nella posizione che gli spetta
    int indice_pivot = inizio + cont;
    swap(v[indice_pivot], v[inizio]);


    // spostiamo gli elementi più piccoli del pivot alla sua sinistra
    // e quelli più grandi alla sua destra
    int i = inizio, j = fine;

    while (i < indice_pivot && j > indice_pivot) {

        while (v[i] <= pivot) {
            i++;
        }

        while (v[j] > pivot) {
            j--;
        }

        if (i < indice_pivot && j > indice_pivot) {
            swap(v[i], v[j]);
            i++; j--;
        }
    }
    //cout << string(40, '-') << "\n\n";

    return indice_pivot;
}

void quickSort(string v[], int inizio, int fine)
{

    if (inizio >= fine)
        return;


    int p = partiziona(v, inizio, fine);

  //tail recursion
  // ordina la parte a sinistra
    quickSort(v, inizio, p - 1);

    // ordina la parte a destra
    quickSort(v, p + 1, fine);

}

int ricerca_sequenziale(string cercata, string v[], int num_ele)
{
  for (int i=0; i<num_ele; i++)
    if (cercata==v[i]) return i;

  return -1;
}

int ricerca_binaria(string cercata, string v[], int num_stringhe)
{
   int inizio = 0;
   int fine = num_stringhe - 1;
   int pos_trovata = -1;

   while (inizio<=fine && pos_trovata==-1)
   {
     int mediano = (inizio+fine)/2;

     if (v[mediano] == cercata)
      pos_trovata=mediano;
     else
       if (v[mediano]<cercata)
         inizio = mediano+1;
       else
        fine = mediano - 1;
   }

   return pos_trovata;
}

int main()
{
  //quante parole contiene il dizionario? 481.816
  int numero_parole_vocabolario = leggi_file("vocabolario3.txt", vocabolario, MAX_PAROLE);


  //scegliamo tra queste 100000 parole da far poi cercare
  //(ammesse ripetizioni della stessa ricerca)
  for (int i=0; i<MAX_CERCATE; i++)
    da_cercare[i] = vocabolario[(rand()*rand()) % numero_parole_vocabolario];

  //sequenziale
  Cronometro(Stato::START);

  for (int i=0; i<MAX_CERCATE; i++)
    ricerca_sequenziale(da_cercare[i], vocabolario, numero_parole_vocabolario);

  cout << "Tempo ricerca sequenziale: " << Cronometro(Stato::STOP) <<"ms\n";

   //binaria
  Cronometro(Stato::START);

  for (int i=0; i<MAX_CERCATE; i++)
    ricerca_binaria(da_cercare[i], vocabolario, numero_parole_vocabolario);

  cout << "Tempo ricerca binaria: " << Cronometro(Stato::STOP) <<"ms\n";


    return 0;
}