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:

1. What is a Linear Search Algorithm?
2. Algorithm and steps to implement the Linear Search.
3. 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:

1. Take the size of the array, the element that needs to be searched, and elements of the array as input from the user.
2. Before searching store the index as -1 in variable names “ans”.
3. Loop through the elements of the array.
4. If a match is found, then we break the loop and update the value of the “ans” variable with the index of the element.
5. 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