Ricerca binaria C++ STL

Harshit Jindal 12 ottobre 2023
  1. C++ STL binary_search() Panoramica
  2. Programma C++ per la ricerca binaria
Ricerca binaria C++ STL
Nota
Se desideri comprendere in dettaglio la ricerca binaria, fai riferimento all’articolo algoritmo di ricerca binaria.

Il C++ ci fornisce una funzione pronta per l’uso binary_search() in modo da non dover implementare la funzione da soli. È un metodo molto semplice da usare e implementato in modo efficiente e non soggetto a errori.

C++ STL binary_search() Panoramica

Sintassi

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);

Qui, T può essere uno dei seguenti: int, float, short, long, byte, char, double e persino un Object definito dall’utente come bene.

Controlla se un elemento all’interno di [first, last) corrisponde all’elemento di destinazione X utilizzando l’algoritmo di ricerca binaria. Per impostazione predefinita, utilizza l’operatore minore di per confrontare gli elementi, ma possiamo anche fornire il nostro comp personalizzato come descritto nel secondo modello fornito sopra.

Parametri

first Un iteratore in avanti che punta verso il primo elemento nell’intervallo di array specificato.
last Un iteratore in avanti che punta verso l’ultimo elemento nell’intervallo di array specificato.
comp Una funzione di predicato binario definita dall’utente che accetta due iteratori in avanti come argomenti e restituisce true se i due argomenti sono presenti nell’ordine corretto. Non modifica alcun argomento e segue l’ordine rigoroso e debole per ordinare gli elementi.
val L’elemento di destinazione che stiamo cercando all’interno dell’intervallo di array specificato.

Ritorno

Se trova l’elemento di destinazione, restituisce true; altrimenti restituisce falso.

Programma C++ per la ricerca binaria

#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

Articolo correlato - C++ Algorithm