1.8K

Here In this article I’m going to discuss about one of the searching technique, Linear Search. And it’s implementation is C programming language.

Searching Problem:

The Searching is the one of the popular computation problem. Searching means identifying the location of something that may be a element in a set or the cafe in street. In computer science, Searching is the process of identifying location of given element in a composite data type. Here Arrays, Matrices, Records or any kind of collection are composite data types.

Technique of Searching is important and useful in any kind of algorithm, that my be simple statistical calculation, Or general classification algorithm or in Complex Deep learning algorithms.

There are many methods to search an element in the composite data structure. But here I only focus to Linear Search. Before Meshing in Linear Search I want to inform you about Types of searching just for knowledge.

Types Of Searching

We can divide searching problems in two categories. This classification of searching problem depends on location of the data.

• External Searching: Here data reside on the external storage like hard disk.
• Internal Searching: Here data reside on the internal storage i.e. RAM

Now lets about Linear Search:

Linear Search:

Linear Search is an easiest and least efficient searching technique. It is also called Sequential Search. This technique is simple in the sense that each elements are accessed one by one and compared until the target is found.

At the time of sequential access media, People used Linear search to find content from magnetic tape. We also can use this technique in direct access media like hard disk for searching.

It is worthless to present algorithm because I’m writing entire code here. Even though I’m gonna write algorithm here just for documentation.

Algorithm:

LinearSearch (DataStructure, target, Size)

step1: Initialize position=0

step2: Repeat WHILE value at position of DataStructure is not equal to target

Step3: IF position is equal to Size then Return -1 

Step4: Otherwise increase position by 1

step5: End of IF

step6: End Of WHILE

step7: Return position;

step8: stop

Now it is time to go for code implementing this algorithm. Here I used integer array as composite data structure that contain multiple integer values. So here we will write code to find the position of target value in the array.

Code:

#include<stdio.h>
#include<conio.h>

int linearSearch(int array[],int target, int size){	
	int position=0;
	while(array[position]!=target){
		if(position==size){
			return -1;
		}else{
			
			position++;
		}
	
	}
return position;
}

void main(){
	int arr[]={12,3,4,5,6,11,4};
	int s=7;
	int t=11;
	int p=linearSearch(arr,t,s);
	if(p==-1){
		printf("%d is not in the array",t);
	}else{
		printf("%d is found at %d position",t,p);
	}
	getch();
}

In the above program the function with name linearSearch contains the implementation of above algorithm. We passed the array, target element and size of the the array. This function will return -1 if the element is not present in that array. Otherwise it will return the index of the target element in array.

Output:

10 is not in the array

Complexity Analysis:

It is clear that we can search in a single step target is in first position or Searching can take n step if target is in n^th position. So We can say it takes O(n) time to perform linear search. We can do search even in less time so this is not regarded as best practice of searching. Little difference in the time complexity affect the speed largely when there is huge input. You must have to understand the value of single read operation. It’s almost nothing when we have data in internal memory but when we are searching on external file system or any remote location single read step can be very costly.

Thank you readers for being here. You can ask or discuss in comment section as well as you can mail us.