Find index of an element in an Array in C++

In this article, we will discuss different ways to find the index of an element in an array in C++.

Table of Contents

Here we are given an array and we have to find index of a element,

Input

int arr[] = {12, 56, 823, 7, 1023};

Output

Index of 56 is 1

There are two method to find index of an element in an array in C++. Let’s discuss them one by one.

Find index of element in Array using Linear traversal (Iterative Method)

In this method, we will iterate over the whole array and look for element in the array.

Steps are as follow:

1. Firstly create a local variable index.
2. Initialize the index with -1.
3. Traverse the whole array:
   1. If the current value is equal to the given value then replace the index value
   2. Break the loop.
4. Print index value

Time Complexity: O(n)
Space Complexity: O(1)

Example

// C++ program to find index of an element

#include <iostream>

using namespace std;

// Driver Code
int main()
{
    int arr[] = {12, 56, 823, 7, 1023};

    // n is the size of array 
    int n = sizeof(arr) / sizeof(arr[0]);

    //Intialize the value of index
    int index = -1;

    // Let's suppose we have to find index of 56
    int element = 56;

    // Iterate the array
    for(int i=0;i<n;i++)
    {
        if(arr[i]==element)
        {
            //If current value is equal to our element then replace the index value and break the loop
            index = i;
            break;
        }
    }

    if(index==-1)
    {
        cout<<"Element doesn't exist in array" <<endl;
    }
    else
    {
        cout << "Index of " << element<<" is "<< index << endl;
    }
    return 0;
}

Output

Index of 56 is 1

Let’s take another example where element doestn’t exist

// C++ program to find index of an element

#include <iostream>

using namespace std;

// Driver Code
int main()
{
    int arr[] = {12, 56, 823, 7, 1023};

    // n is the size of array 
    int n = sizeof(arr) / sizeof(arr[0]);

    //Intialize the value of index
    int index = -1;

    // Let's suppose we have to find index of 55
    int element = 55;

    // Iterate the array
    for(int i=0;i<n;i++)
    {
        if(arr[i]==element)
        {
            //If current value is equal to our element then replace the index value and break the loop
            index = i;
            break;
        }
    }

    if(index == -1)
    {
        cout<<"Element doesn't exist in array" <<endl;
    }
    else
    {
        cout << "Index of " << element<<" is "<< index << endl;
    }
    return 0;
}

Output

Element doesn't exist in array

Note

1. If we don’t find the element in the array, means it doesn’t exist then the index value would be -1.

Find index of element in Array using STL function std::find()

In this method we use STL function to find the index of an element.

STL function is : find()

Time Complexity: O(n)
Space Complexity: O(1)

It accepts a range and element to be found in that range as arguments. Then returns the address of given element in the array. If element does not exist then it returns the address of next to last element in array.

Example

// STL Function to find index of a element
#include <iostream>
#include <algorithm>

using namespace std;

// Driver Code
int main()
{
    int arr[] = {12, 56, 823, 7, 1023};
    int n = sizeof(arr) / sizeof(arr[0]);

    int element = 56;

    // using stl function
    int index = find(arr, arr + n, element) - arr;

    if (index < n)
    {
        cout << "Index of " << element<<" is "<< index << endl;
    }
    else
    {
        cout<< "Element does not exist in array" << endl;
    }

    return 0;
}

Output

Index of 56 is 1

Let’s take another example where element doestn’t exist

// STL Function to find index of a element
#include <iostream>
#include <algorithm>

using namespace std;

// Driver Code
int main()
{
    int arr[] = {12, 56, 823, 7, 1023};
    int n = sizeof(arr) / sizeof(arr[0]);

    int element = 55;

    // using stl function
    int index = find(arr, arr + n, element) - arr;

    if (index < n)
    {
        cout << "Index of " << element<<" is "<< index << endl;
    }
    else
    {
        cout<< "Element does not exist in array" << endl;
    }

    return 0;
}

Output

Element does not exist in array

Explaination

An element doest not exist in the array then find() function return the last iterator or address of element next to last in the array. We subtracted that with the address of fist element of array, and it returned a number which was greater than the size of array. This proved that element doesn’t exist in the array.

Summary

We have seen two different method to find index of an element and also seen what happend if a element does not not exist in array. One is naive solution. Another one is using STL function. Every Method has it’s own time complexity and space complexity.