Linear Search

Linear search –

We traverse an array / list elements, one by one to search a given number till the end of the array / list until element is found.

Key point – Checking each element of the list until the desired element is found.

Example – Suppose that we want to find the number 3.8 in the following list:

[1.5, 2.7, 3.8, 7.2]

1.  We start with the first element, and perform a comparison to see if its value is the value that we want. In this case, 1.5 is not equal to 3.8, so we move onto the next element.
2. We perform another comparison, and see that 2.7 is also not equal to 3.8, so we move onto the next element.
3. We perform another comparison and determine that we have found the correct element. Now we end the search and return the position of the element (index 2).

Observations:   We had to use a total of 3 comparisons when searching through this list of 4 elements.

Note : How many comparisons we need to perform depends on the total length of the list, but also whether the element we are looking for is near the beginning or near the end of the list. In the worst-case scenario, if our element is the last element of the list, we will have to search through the entire list to find it.

If we search the same list many times, assuming that all elements are equally likely to be searched for, we will on average have to search through half of the list each time. The cost (in comparisons) of performing linear search thus scales linearly with the length of the list.

Time Complexity : The time complexity of linear search is

Worst Case

Time Complexity: O(N)

When the search value is not present in the array

Best Case

Time Complexity: O(1)

When the search value is the first element of the array.

Average Case

This is a little different.

Let N be the size of the array.

Let X be the value we want to search for.

Now,

Number of Comparisons when X is at 0th index = 1

Number of Comparisons when X is at 1st index = 2

Number of Comparisons when X is at 2nd index = 3

……

Number of Comparisons when X is at (N-1) index = N

Average Comparisions = (Sum of Comparisons at all indices) / N

Average Comparisions = (1+2+3+….+N) = (N(N+1)/2)/N = (N+1)/2

Time Complexity = O((N+1)/2)

But since we ignore constant

Time Complexity = O(N)

Code : Linear Search code is written below-


#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
int key;
cin>>key;
int ind=-1;
for(int i=0;i<n;i++){
if(arr[i] == key){
ind=i;
break;
}
}
cout<<ind<<endl;
return 0;
}