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
Frequently Asked:
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:
- Firstly create a local variable index.
- Initialize the index with -1.
- Traverse the whole array:
- If the current value is equal to the given value then replace the index value
- Break the loop.
- Print index value
Time Complexity: O(n)
Space Complexity: O(1)
Best Resources to Learn C++:
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
- 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.