Linear Search : Technique, Program, Algorithm & Complexity

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:
  

            int a[5]={22,5,3,15,7};

• 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.

item=15

• 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).