Searching in Array in C++
In this tutorial, we are going to learn about Searching in Array in C++. We’ll be using an algorithm called Linear Search for this purpose.
Linear search is a basic and simple search algorithm. We’ll also implement a C++ Program, that performs the searching task using Linear Seach. The topics that are covered in this tutorial are as follows:
- What is a Linear Search Algorithm?
- Algorithm and steps to implement the Linear Search.
- Coding Linear Search in C++ for an array.
Linear Search Definition:
A linear search, also known as a sequential search, is a method of finding an element within an array. It checks each element of the array sequentially until a match is found for a particular element or the whole array has been searched.
Time and Space Complexity analysis of this method:
- Worst Case Time Complexity – O(n)
- Best Case Time Complexity – O(1)
- Average Time Complexity – O(n)
- Worst Case Space Complexity – O(1) Iterative
Algorithm:
- Take the size of the array, the element that needs to be searched, and elements of the array as input from the user.
- Before searching store the index as -1 in variable names “ans”.
- Loop through the elements of the array.
- If a match is found, then we break the loop and update the value of the “ans” variable with the index of the element.
- If no match is found, then display output accordingly.
Code:
#include<iostream> using namespace std; int main() { int n,k,ans=-1; cout<<"Enter size of array"<<endl; cin>>n; int arr[n]; cout<<"Enter elements of array"<<endl; for(int i=0;i<n;i++) { cin>>arr[i]; } cout<<"Enter element to be searched"<<endl; cin>>k; for(int i=0;i<n;i++) { if(arr[i]==k) { ans=i; break; } } if(ans!=-1) cout<<"The element "<<k<<" is present at index "<<ans; else cout<<"The element "<<k<<" is not there in the array"; return 0; }
Output: Enter size of array 5 Enter elements of array 10 20 30 40 50 Enter element to be searched 30 The element 30 is present at index 2
Leave a Reply