Linear Search
Introduction:
When we have to check where the element ( the key ) is present in the array, the first naive method is to compare every element with the key and return that index of array of present.
Problem Statement:
search for an element in an array
Algorithm
1. we have an array of n numbers and a key k to seach for.
2. we go through the array comparing every element with key.
3. If we find a match then we return the index at that point or else we meet the end of array and we return \(-1\) implying no success or no such element in array.
Code :
#include <bits/stdc++.h>
using namespace std;
int linear_search(int a[], int n, int key)
{
for (int i = 0; i < n; i++)
{
if (a[i] == key)
{
return i;
}
}
return -1;
}
int main()
{
int n;
cout << "Enter n: ";
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int key;
cout << "key: ";
cin >> key;
int position = linear_search(a, n, key);
if (position < 0)
{
cout << key << " is not found in the list\n";
}
else
{
cout << key << " occurs at position " << position << " in 0 based indexing\n";
}
}
Complexity Analysis :
Time complexity is \(O(n)\)