Implementa la ricerca binaria in C++

1. Implementare l’algoritmo di ricerca binaria per il contenitore std::vector in C++
2. L’analisi della complessità dell’algoritmo di ricerca binaria

Questo articolo spiegherà come implementare l’algoritmo di ricerca binaria in C++.

Implementare l’algoritmo di ricerca binaria per il contenitore std::vector in C++

Gli algoritmi di ricerca sono subroutine fondamentali utilizzate nei problemi più comuni ed è importante eseguirli nel modo più efficiente. Esistono vari tipi di algoritmi di ricerca; alcuni sono personalizzati per strutture dati speciali e altri possono essere applicati più in generale.

La ricerca binaria è un algoritmo di tipo divide et impera che deve essere utilizzato su un array ordinato di chiavi. Viene spesso chiamata ricerca logaritmica a causa delle sue prestazioni nel caso peggiore, di cui parleremo più avanti nell’articolo.

Puoi descrivere la ricerca binaria come segue: Una volta che abbiamo l’array ordinato di oggetti in cui deve essere trovata la chiave k, dovremmo confrontare la chiave data con l’elemento centrale nell’array. Se la chiave è minore dell’elemento, dovrebbe trovarsi nella metà sinistra dell’array, o se è più grande, dovremmo cercarla nella metà destra.

Dopo aver ripetuto questo processo di ricerca in modo ricorsivo su ogni semiarray più piccolo, alla fine troveremo la posizione della chiave o indicheremo che la chiave non è nella matrice. Anche se descriviamo l’algoritmo come ricorsivo naturale, può essere implementato utilizzando il metodo iterativo, ma ci concentreremo su quello ricorsivo.

Il seguente codice di esempio genera un migliaio di interi casuali nell’intervallo [1-1000] e li memorizza nel contenitore std::vector. Il vettore viene quindi ordinato utilizzando l’algoritmo std::sort e dichiariamo un altro vettore di nove interi da cercare. Si noti che la funzione wrapper searchVector viene utilizzata per chiamare la funzione ricorsiva binarySearch.

Quest’ultimo controlla se il primo degli indici a due posizioni è maggiore dell’altro; in caso affermativo, la funzione restituisce. Il valore di ritorno -1 viene utilizzato per indicare lo stato non trovato per la chiave data. Successivamente, viene calcolata la posizione centrale e confrontata con la chiave, che restituisce il valore dell’indice se vero. Infine, scegliamo quale parte dell’array deve essere cercata e chiamiamo la stessa funzione con gli indici corrispondenti.

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;

template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
  if (s1 > s2) return -1;

  auto middle = (s1 + s2) / 2;

  if (item == vec.at(middle)) return middle;

  if (item > vec.at(middle))
    return binarySearch(vec, item, middle + 1, s2);
  else
    return binarySearch(vec, item, s1, middle - 1);
}

template <typename T>
int searchVector(const vector<T> &vec, T &item) {
  return binarySearch(vec, item, 0, vec.size() - 1);
}

int main() {
  std::random_device rd;
  std::default_random_engine eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  std::vector<int> vec;
  vec.reserve(NUMS_TO_GEN);
  for (int n = 0; n < NUMS_TO_GEN; ++n) {
    vec.push_back(distr(eng));
  }
  std::sort(vec.begin(), vec.end());

  std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
  for (auto &item : vec2) {
    searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
  }
  cout << endl;

  return EXIT_SUCCESS;
}

Produzione:

did not, found, found, did not, found, did not, found, did not, found,

L’analisi della complessità dell’algoritmo di ricerca binaria

La ricerca binaria ha la complessità O(log n), da cui il nome alias - ricerca logaritmica. Possiamo stimare in modo approssimativo il tempo di esecuzione delle implementazioni di algoritmi ricorsivi analizzando il costo di ricorrenza. Nota che cercare l’elemento centrale è un’operazione a tempo costante e dobbiamo attraversare metà dell’array.

Nel seguente programma, dimostriamo il test di verifica per la nostra funzione di ricerca binaria utilizzando l’algoritmo STL std::sort. Tieni presente, tuttavia, che questo controllo non è una verifica formale e fornisce solo un rapido test case durante il processo di implementazione dell’algoritmo per eseguire il debug e analizzare il comportamento del codice.

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;

template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
  if (s1 > s2) return -1;

  auto middle = (s1 + s2) / 2;

  if (item == vec.at(middle)) return middle;

  if (item > vec.at(middle))
    return binarySearch(vec, item, middle + 1, s2);
  else
    return binarySearch(vec, item, s1, middle - 1);
}

template <typename T>
int searchVector(const vector<T> &vec, T &item) {
  return binarySearch(vec, item, 0, vec.size() - 1);
}

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  std::vector<int> vec;
  vec.reserve(NUMS_TO_GEN);
  for (int n = 0; n < NUMS_TO_GEN; ++n) {
    vec.push_back(distr(eng));
  }
  std::sort(vec.begin(), vec.end());

  std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
  for (auto &item : vec2) {
    searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
  }
  cout << endl;

  for (auto &item : vec2) {
    std::find(vec.begin(), vec.end(), item) != vec.end() ? cout << "found, "
                                                         : cout << "did not, ";
  }

  return EXIT_SUCCESS;
}

Produzione:

found, found, found, found, did not, did not, found, found, found, found, found,
    found, found, did not, did not, found, found, found,