Implémenter la recherche binaire en C++

1. Implémenter l’algorithme de recherche binaire pour le conteneur std::vector en C++
2. L’analyse de complexité de l’algorithme de recherche binaire

Cet article explique comment implémenter l’algorithme de recherche binaire en C++.

Implémenter l’algorithme de recherche binaire pour le conteneur std::vector en C++

Les algorithmes de recherche sont des sous-routines fondamentales utilisées dans la plupart des problèmes courants, et il est important de les exécuter de la manière la plus efficace. Il existe différents types d’algorithmes de recherche ; certains sont adaptés à des structures de données spéciales et d’autres peuvent être appliqués de manière plus générale.

La recherche binaire est un algorithme de type diviser pour régner qui doit être utilisé sur un tableau trié de clés. On l’appelle souvent une recherche logarithmique en raison de ses performances dans le pire des cas, que nous verrons plus loin dans l’article.

Vous pouvez décrire la recherche binaire comme suit : Une fois que nous avons le tableau trié d’objets où la clé k doit être trouvée, nous devons comparer la clé donnée à l’élément central du tableau. Si la clé est inférieure à l’élément, elle doit être située dans la moitié gauche du tableau, ou si elle est plus grande, nous devons la rechercher dans la moitié droite.

Après avoir répété ce processus de recherche de manière récursive sur chaque demi-tableau plus petit, nous finirons par trouver la position de la clé ou indiquer que la clé n’est pas dans le tableau. Même si nous décrivons l’algorithme comme naturellement récursif, il peut être implémenté en utilisant la méthode itérative, mais nous nous concentrerons sur la récursive.

L’exemple de code suivant génère un millier d’entiers aléatoires dans la plage [1-1000] et les stocke dans le conteneur std::vector. Le vecteur est ensuite trié à l’aide de l’algorithme std::sort, et nous déclarons un autre vecteur de neuf entiers à rechercher. Notez que la fonction wrapper searchVector est utilisée pour appeler la fonction récursive binarySearch.

Ce dernier vérifie si le premier des indices à deux positions est supérieur à l’autre ; si c’est le cas, la fonction retourne. La valeur de retour -1 est utilisée pour indiquer l’état non trouvé pour la clé donnée. Ensuite, la position médiane est calculée et comparée à la clé, qui renvoie la valeur d’index si elle est vraie. Enfin, nous choisissons quelle partie du tableau doit être recherchée et appelons la même fonction avec les indices correspondants.

#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;
}

Production:

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

L’analyse de complexité de l’algorithme de recherche binaire

La recherche binaire a la complexité O(log n), d’où le nom d’alias - recherche logarithmique. Nous pouvons vaguement estimer le temps d’exécution des implémentations d’algorithmes récursifs en analysant le coût de récurrence. Notez que la recherche de l’élément du milieu est une opération à temps constant et que nous devons parcourir la moitié du tableau.

Dans le programme suivant, nous démontrons le test de vérification de notre fonction de recherche binaire en utilisant l’algorithme STL std::sort. Gardez à l’esprit, cependant, que cette vérification n’est pas une vérification formelle et fournit simplement un cas de test rapide pendant le processus d’implémentation de l’algorithme pour déboguer et analyser le comportement du code.

#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;
}

Production:

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