C++ Standard Library C++ STL Library

C++ <algorithm> - search() Function



The C++ algorithm::search function is used to search the range [first1,last1) for the first occurrence of the sequence defined by [first2,last2). The function returns an iterator pointing to the first element of the sequence if found in the range, else pointing to the last1.

Syntax

//equality version
template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2);

//predicate version
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2,
                            BinaryPredicate pred);

Parameters

first1 Specify initial position of the forward iterator of the searched sequence. The range used is [first1,last1).
last1 Specify final position of the forward iterator of the searched sequence. The range used is [first1,last1).
first2 Specify initial position of the forward iterator of the sequence to be searched for. The range used is [first2,last2).
last2 Specify final position of the input iterator of the sequence to be searched for. The range used is [first2,last2).
pred Specify a binary function that accepts two element as argument (one of each of the two sequences, in the same order), and returns a value convertible to bool. The function returns true if the elements are considered to match in the context of this function.

Return Value

Returns an iterator to the first element of the first occurrence of [first2,last2) in [first1,last1). If the sequence is not found, the function returns last1.

Time Complexity

Up to Linear i.e, Θ(n).

Example:

In the example below, the algorithm::search function is used to check whether the given sequence is present in the given range or not.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
  vector<int> MyVec= {10, 20, 30, 40, 50, 60, 70, 80};
  vector<int> v1 = {30, 40};
  vector<int> v2 = {30, 60};
  vector<int>::iterator it;

  //search for v1 sequence in MyVec
  it = search(MyVec.begin(), MyVec.end(), v1.begin(), v1.end());

  if(it != MyVec.end()) {
    cout<<"v1 is found at position="<<(it-MyVec.begin())<<" in MyVec.\n";
  } else {
    cout<<"v1 is not found in MyVec.\n";
  }

  //search for v2 sequence in MyVec
  it = search(MyVec.begin(), MyVec.end(), v2.begin(), v2.end());

  if(it != MyVec.end()) {
    cout<<"v2 is found at position="<<(it-MyVec.begin())<<" in MyVec.\n";
  } else {
    cout<<"v2 is not found in MyVec.\n";
  }

  return 0;
}

The output of the above code will be:

v1 is found at position=2 in MyVec.
v2 is not found in MyVec.

Example:

The example below shows how to use predicate with algorithm::search function.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool eq (int i, int j) {
  return (i==j);
}

int main (){
  vector<int> MyVec= {10, 20, 30, 40, 50, 60, 70, 80};
  vector<int> v1 = {30, 50};
  vector<int> v2 = {60, 70, 80};
  vector<int>::iterator it;

  //search for v1 sequence in MyVec
  it = search(MyVec.begin(), MyVec.end(), v1.begin(), v1.end(), eq);

  if(it != MyVec.end()) {
    cout<<"v1 is found at position="<<(it-MyVec.begin())<<" in MyVec.\n";
  } else {
    cout<<"v1 is not found in MyVec.\n";
  }

  //search for v2 sequence in MyVec
  it = search(MyVec.begin(), MyVec.end(), v2.begin(), v2.end(), eq);

  if(it != MyVec.end()) {
    cout<<"v2 is found at position="<<(it-MyVec.begin())<<" in MyVec.\n";
  } else {
    cout<<"v2 is not found in MyVec.\n";
  }

  return 0;
}

The output of the above code will be:

v1 is not found in MyVec.
v2 is found at position=5 in MyVec.

❮ C++ <algorithm> Library

5