Difference between revisions of "Linear Search"

Revision as of 23:32, 2 December 2016

Linear Search

This Searching Algorithm starts at the very first element of the list and checks every element there on till the required data in the element is fetched or the list ends. This Searching is natural and is in a sequential manner and therefore called "Sequential Search" as well. Therefore this algorithm is very slow in order O(n) of Big O notation but works well on an unsorted list.

Regardless of the search algorithm implemented on an array or linked list the critical part is the comparison loop. Lesser the number of comparison, sooner the termination of the loop. Minimum possible comparisons=1, i.e when the required element is the first element in the array. Maximum possible comparisons=N, i.e. when the required element is the last element in the array. So, the average number of comparisons done by Linear search =(1+2+3+...+N)/N =N(N+1)/2*N =(N+1)/2 , where N is the size of the array.

Hence Linear Search works well for short data sets and is disastrous for lengthy data sets regardless of data being sorted.

Code Snippet

#include <stdio.h>

/* Linear Search function to search for a key in the List */

int seq_search(int key, int array[], int size)
{

	for (int i = 0; i < size; i++)                                  //looping over the array to find the matching element
	{
		if(array[i] == key) return i + 1;                       //returning the position of the matched element
	}
	return 0;	                                                // returning 0 or the beginning of array, stating element was not found
}

int main()
{
	int  size, key, pos;			                        
	printf("Enter the size of Array\n");
	scanf("%d", & size);				                // defining the array size
	int array[size];

	printf("Enter %d values for the array\n",size);
	for (int i = 0; i <size; i++)
	{
		scanf("%d", & array[i]);				// Setting the array elements
	}

	printf("Enter the key to be searched\n");
	scanf("%d", & key);						// Keying in the value which has to be searched

	pos = seq_search(key,array,size);				// Calling the Linear search function
	if (pos == 0)							// If position of the searching stays at 0 element or beginning
	printf("Search unsuccessful, element not found in array");
	else
		printf("key %d found at position = %d",key,pos);        //Printing the value fetched
	return 0;
}