Linear Search Technique
- Suppose you have a single key which may or may not open one of the five doors given below.
- We can try to unlock doors one by one randomly.
- Or we can also start from either end and try to unlock doors in a sequential order, this is known as linear search.
- If one of the doors is unlocked then search is successful otherwise search is unsuccessful.
- This algorithm search an element in a given list by comparing an item with each of the elements of list one by one.
- We can start from first element and search upto last element (o to n-1).
- Or we can also start from the last element and search till the first element (n-1 to 0).
- In both of the cases each location of the array is searched once.
- Suppose we want to find location of element 15 in Array given below:
- We will start comparing 15 with each of the elements of array one by one starting from a[0] to a[4].
- If element is found then we will return its location otherwise we will return-1 treated as an invalid index of Array.
- Firstly we will compare 15 with a[0] i.e. 22 which are not equal so, we will compare it with next element a[1] i.e. 5, again both are not equal.
- We will continue our search process until we find our element or if we exceed upper bound of our Array.
- In our case item is found at index "3" of given array so, 3 will be returned. item=15
- There might be situation where array elements are duplicate in that case our algorithm will return the index of first occurrence.
- If given element is not present in the list then our algorithm will return-1 which is treated as an invalid array index in our case.
Let us take another Example
- In this case "2" will be returned as first occurrence of 15 is found at index 2 of our given Array.
- In this case -1 will be returned as element is not present in our Array.
Linear Search C Program
#include<stdio.h>
#include<conio.h>
int linear_search(int a[],int n,int item)
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==item)
return i;
}
return -1;
}
void main()
{
int i,a[5]={22,5,3,15,7},k,loc;
clrscr();
printf("Enter element to be searched:: ");
scanf("%d",&k);
loc=linear_search(a,5,k);
if(loc==-1)
printf("Element not found");
else
printf("Element found at %d ",loc);
getch();
}
Linear Search Time Complexity
Best Case:
- In Best case item will be found in only one comparison i.e. at "0" index of the array. So, it is constant i.e. o(1).
Worst Case:
- In Worst case either item will be found at last index of Array i.e. "n-1" or item is not present in the Array both of which requires total of "n" comparisons. So, it is O(n).
Average Case:
- If element is found at location "0" then it will take 1 comparison
- if it is found at location 1" then it will take 2 comparisons
- if it is found at location "n-1 then it will take 'n" comparisons.
Average (1+2+3+..+n)/n = (n*(n+1))/2n =(n+1)/2=0(n).
