How to check if a vector contains a particular value in C++

Finding whether a vector contains a particular value, can be done in linear time if it’s a random vector. If it’s known that the vector is sorted then this can be further optimized to logarithmic time complexity.

In this article, both versions are demonstrated.

For a random vector:

For the random vector, the optimal algorithm for checking whether it contains a particular value is linear searching the vector until the value is found. If we reach the end of the vector, then the vector doesn’t have the value.

The following code demonstrates the point:

#include <iostream>
#include <vector>
bool find(std::vector<int>& a, int value)
{
  bool contains{ false }; // becomes true if it contains the value
  for (int i = 0; i < a.size(); i++)
  {
    if (a[i] == value) // checks for the presence of the value in the vector
    {
      contains = true; break;
    }
  }
  return contains;
}
int main()
{
  std::vector<int> a = { 1,72,33,41,5,86,74 };
  if (find(a, 3))
  {
    std::cout << "The vector contains 3\n";
  }
  else
  {
    std::cout << "The vector doesn't contain 3\n";
  }
  if (find(a, 33))
  {
    std::cout << "The vector contains 33\n";
  }
  else
  {
    std::cout << "The vector doesn't contain 33\n";
  }
}

 

Output:
The vector doesn't contain 3
The vector contains 33

The STL has a function called find() which returns an iterator to the element to be found in a range.

The syntax for the function is:

std::find(start_point iterator,end_point iterator,value);

The find function works in the range[start, end). This function can be used to check for the existence of a value by checking it with the value it returns to the end iterator of the vector. The find() function returns the end iterator if the value is not found.

The following code illustrates the point:

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
  std::vector<int> a = { 1,72,33,41,5,86,74 };
  int value=33; //value to be found
  auto find3=std::find(a.begin(),a.end(),value);
  if(find3==a.end())
  {
      std::cout<<"The vector doesn't contain the value"<<std::endl;
  }
  else
  {
      std::cout<<"The vector contains the value"<<std::endl;
  }
}
Output:
The vector contains the value

For a sorted vector:

Using linear search for a sorted vector will be slower because there is a much better algorithm called binary search which runs in logarithmic time.  The STL provides an implementation of binary search which returns true if the value is present in the range and false otherwise.

The syntax for the function is:

std::binary_search("start_iterator","end_iterator",value);

The following code illustrates the use of the function:

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
  std::vector<int> a = { 1,5,33,41,72,74,86 }; //sorted vector
  int value = 33;
  bool ans = std::binary_search(a.begin(), a.end(), value); // true if value is present in the vector
  if (ans)
  {
    std::cout << "The value is present in the vector\n";
  }
  else
  {
    std::cout << "The value is not present in the vector\n";

  }
}
Output:
The value is present in the vector

Leave a Reply

Your email address will not be published. Required fields are marked *