Recherche dichotomique C++ STL

Harshit Jindal 12 octobre 2023
  1. Vue d’ensemble de C++ STL binary_search()
  2. Programme C++ pour la Recherche dichotomique
Recherche dichotomique C++ STL
Noter
Si vous voulez comprendre la Recherche dichotomique en détail, reportez-vous à l’article algorithme de Recherche dichotomique.

C++ nous fournit une fonction prête à l’emploi binary_search() afin que nous n’ayons pas à implémenter la fonction nous-mêmes. C’est une méthode très simple à utiliser et mise en œuvre efficacement et non sujette aux erreurs.

Syntaxe

DEFAULT
    : template <class ForwardIterator, class T>
      bool
      binary_search(ForwardIterator first, ForwardIterator last, const T& val);

CUSTOM COMPARISON FUNCTION
    : template <class ForwardIterator, class T, class Compare>
      bool
      binary_search(ForwardIterator first, ForwardIterator last, const T& val,
                    Compare comp);

Ici, T peut être l’un des suivants: int, float, short, long, byte, char, double, et même un Object défini par l’utilisateur comme bien.

Il vérifie si un élément à l’intérieur de [premier, dernier) correspond à l’élément cible X en utilisant l’algorithme de Recherche dichotomique. Par défaut, il utilise l’opérateur less-than pour comparer les éléments, mais nous pouvons également fournir notre propre comp personnalisé comme décrit dans le deuxième modèle donné ci-dessus.

Paramètres

first Un itérateur avant pointant vers le premier élément de la plage de tableau donnée.
last Un itérateur vers l’avant pointant vers le dernier élément de la plage de tableau donnée.
comp Une fonction de prédicat binaire définie par l’utilisateur qui accepte deux itérateurs avant comme arguments et renvoie true si les deux arguments sont présents dans le bon ordre. Il ne modifie aucun argument et suit l’ordre strict strict pour ordonner les éléments.
val L’élément cible que nous recherchons dans la plage de tableau donnée.

Revenir

S’il trouve l’élément cible, il renvoie true; sinon, il retourne false.

Programme C++ pour la Recherche dichotomique

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = {1, 2, 3, 4, 5, 6};

  if (binary_search(v.begin(), v.end(), 5)) {
    cout << "Element found" << endl;
  } else {
    cout << "Element not found" << endl;
  }

  return 0;
}
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Article connexe - C++ Algorithm