How to Check if element exist in array in C++?

In this article, we will discuss different ways to check if an element exist in an array or not in C++.

Table Of Contents

Problem Description

Suppose we have an array of n numbers of elements. Our task is to check if a given element exists in the array or not.

  • If the given element exists in array, we have to print Element found.
  • If the given element does not exists in the array, we have to print Element not found.

Input

int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 30;

Output

Element found

We can think of solving the given problem in seven ways. Let’s understand all the approaches in details one by one.

The very first approach that we are going to learn is the Binary Search. The only condition in this approach is that the array has to be sorted. If the array is sorted, then it is the fastest approach to check whether the element is present or not.

Following are the steps involved in the Binary Search Algorithm

  1. After only one comparison, we simply ignore half of the elements.
  2. Compare the mid element to our given element.
  3. We return the mid index if our given element matches with the middle element.
  4. Else If our given element is bigger than the mid element, it can only be found after the mid element in the right half subarray. As a result, we repeat for the right half only, by ignoring the left half subarray.
  5. Otherwise, repeat for the left half, if our given element is smaller than the mid element.
  6. Time Complexity is of order of log n means it is completed in logarithmic time, Time Complexity O(log n).
  7. Space Complexity is of constant order, Space Complexity O(1).

C++ Code for Binary Search Algorithm

// Binary Search Algorithm to check whether an element is exist in array or not.

#include <iostream>
using namespace std;

int main()
{
    // Taking sorted array
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int key = 30;

    int start, end;

    // start pointer points at 0th index.
    start = 0;

    //  end pointer points at 9th index.
    end = 9;


    // Search until the start is less than or equal to end
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (arr[mid] == key)
        {
            cout << " Element found " << endl;
            break;
        }

        // left half subarray
        else if (arr[mid] > key)
        {
            end = mid - 1;
        }

        // right half subarray
        else
        {
            start = mid + 1;
        }
    }

    // check for the condition if element is not found
    if (start > end)
    {
        cout << "Element not found" << endl;
    }

    return 0;
}

Output

Element found

The second approach that we are going to learn is the linear Search. In this approach we iteratively traverse the array until the given specified element is found. In this approach sorted array is not required unlike the binary search algorithm. It is the simplest searching algorithm.

Following are the steps involved in the Linear Search Algorithm.

  1. Starting with the leftmost element of array, compare the given specified element to each element of array one by one.
  2. Come out of the loop if given specified element matches and print Element Found
  3. If given specified element does not match any of the elements and print Element not Found
  4. Time Complexity is of order of n means it is completed in linear time, Time Complexity O(n).
  5. Space Complexity is of constant order, Space Complexity O(1).

C++ Code for Linear Search Algorithm

// Linear Search Algorithm to check whether an element is exist in array or not.

#include <iostream>
using namespace std;

int main()
{

    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 30;
    int i;

    // Iteratively traverse throughout the array
    for (i = 0; i < n; i++)
    {
        // If found than print "Element found " and break the loop.
        if (arr[i] == key)
        {
            cout << "Element found " << endl;
            break;
        }
    }

    // check for the condition if element is not found
    if (i == n)
    {
        cout << "Element not found" << endl;
    }
    return 0;
}

Output

Element Found

Now all the upcoming approaches are based on Standard Template Library (STL) and the predefined function under the algorithm header file.

The third approach that we are going to learn is using the std::binary_search(). If the array is sorted, the std::binary search algorithm is the quickest alternative. If the element is found within the given range, it returns true; otherwise, it returns false. Although,  We can sort an unsorted array before applying the binary search algorithm on it. However, the time complexity grows to O(nlog(n)).

  • Time Complexity is of order of logn means it is completed in logarithmic time, Time Complexity O(log n).
  • Space Complexity is of constant order, Space Complexity O(1).

C++ Code for std::binary_search()

// Using Binary Search algorithm predefined function
// to check whether an element is exist in array or not.

#include <iostream>
#include <algorithm> 

using namespace std;

int main()
{
    // Taking sorted array
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; 
    int key = 30;

    // calculating the number of elements in an array,
    // same as size of array
    int n = sizeof(arr) / sizeof(arr[0]); 

    // calling the function isFound to check whether
    // an element is exist in array or not
    if (n > 0 && std::binary_search(arr, arr + n, key))
    {
        cout << "Element found";
    }
    else
    {
        cout << "Element not found";
    }
    cout<<endl;

    return 0;
}

Output

Element Found

Check if element exist in array using std::find()

The fourth approach that we are going to learn is using the std::find (). It checks if the element exist in an array or not. It is a simple and efficient approach. If the matching element is found, then it returns an iterator to the first occurrence of the given element in array. Whereas, if the given element isn’t found, it provides an iterator to the end of the range. This is the preferred method since the algorithm stops searching once a match is found. 

  • Time Complexity is of order of logn means it is completed in logarithmic time, Time Complexity O(log n).
  • Space Complexity is of constant order, Space Complexity O(1).

C++ Code for std::find()

// Using std::find() predefined function to
// check whether an element is exist in array or not.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    // Input the array
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int key = 30;

    // calculating the number of elements
    // in an array, same as size of array
    int n = sizeof(arr) / sizeof(arr[0]);

    // applying the find() function to check whether
    // an element is exist in array or not
    if (std::find(arr, arr + n, key) != (arr + n) )
    {
        std::cout << "Element found";
    }
    else
    {
        std::cout << "Element not found";
    }
    std::cout<<std::endl;

    return 0;
}

Output

Element Found

Check if element exist in array using any_of() function

The fifth approach that we are going to learn is using the STL Algorithm any_of(). The any_of() function in C++11, returns true if and only if the given predicate is true for any item in the specified range or if the range is empty. Otherwise it returns false.

  • The time complexity of std::any_of() is of order n, means it is completed in linear time. Time Complexity O(n).
  • Space Complexity is of constant order, Space Complexity O(1).

C++ Code for std::any_of()

// Using std::any_of() predefined function to
// check whether an element is exist in array or not.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    // Input the array
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int key = 30;

    // calculating the number of elements in 
    // an array, same as size of array
    int n = sizeof(arr) / sizeof(arr[0]);

    // applying the any_of() function to check whether
    // an element is exist in array or not.
    bool found = std::any_of(begin(arr),
                             end(arr),
                             [&](int i) {
                                return i == key;
                            });

    // checking the bool found variable value
    if (found)
    {
        std::cout << "Element found";
    }
    else
    {
        std::cout << "Element not found";
    }
    std::cout<< std::endl;

    return 0;
}

Output

Element Found

Check if element exist in array using boost::algorithm::any_of_equal() function

The sixth approach that we are going to learn is using the boost::algorithm::any_of_equal() function. One efficient option is to use the C++ boost library. The boost::algorithm::any_of_equal() function is defined in the header boost/algorithm/cxx11/any of.hpp. It takes a sequence and a value, and returns true if any of the items in an array equals the target/key value.

** Dont worry if this code is not running or throw some error, it is because the boost library is not installed on your machine, you can refer the article for how to setup the boost library.

  • The time complexity of std::any_of_equal() is of order n, means it is completed in linear time. Time Complexity O(n).
  • Space Complexity is of constant order, Space Complexity O(1).

C++ Code for std::any_of_equal()

// Using std::any_of_equal() predefined function
// to check whether an element is exist in array or not.

#include <iostream>
#include <boost/algorithm/cxx11/any_of.hpp>

using namespace std;

int main()
{
    // Input the array
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int key = 30;

    // calculating the number of elements in an array,
    // same as the size of array
    int n = sizeof(arr) / sizeof(arr[0]);

    // applying the any_of_equal() function to check
    // whether an element is exist in array or not
    if (boost::algorithm::any_of_equal(arr, key))
    {
        std::cout << "Element found";
    }
    else
    {
        std::cout << "Element not found";
    }
    std::cout<< std::endl;

    return 0;
}

Output

Element Found

Check if element exist in array using std::count() function

The seventh and last approach that we are going to learn is using the std::count() function. Using the standard algorithm std::count(), which returns the number of elements that match a value within a given range. This is slower than the std::find() function because it may end up traversing the entire array to get the element’s count.

  • The time complexity of std::count() is of order n, means it is completed in linear time. Time Complexity O(n).
  • Space Complexity is of constant order, Space Complexity O(1).

C++ Code for std::count()

// Using std::count() predefined function to check
// whether an element is exist in array or not.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    // Input the array
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int key = 30;

    // calculating the number of elements in an array, same as size of array
    int n = sizeof(arr) / sizeof(arr[0]);

    // applying the count() function to check whether
    // an element is exist in array or not.
    if ( std::count(begin(arr), end(arr), key) > 0 )
    {
        std::cout << "Element found";
    }
    else
    {
        std::cout << "Element not found";
    }
    std::cout << std::endl;

    return 0;
}

Output

Element Found

Summary

We have seen a detailed explanation of seven approaches to check whether an element exist in an array or not. The first one is using the Binary Search, second is Linear Search, third one is Using std::binary_search() , fourth one is using the std::find(), fifth one is using the any_of() function, sixth one is Using boost::algorithm::any_of_equal() function and the last one is using the std::count(). Also, we have seen the detailed explanation, working, code, Time and Space Complexity of all the seven approaches. Happy Coding.

Leave a Comment

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top