Linear Search - Revision history

Proj user16 at 22:55, 8 December 2016

2016-12-08T22:55:21Z

Proj user16 at 08:21, 7 December 2016

2016-12-07T08:21:04Z

Preet: /* Linear Search */

2016-12-07T03:42:22Z

‎Linear Search

Proj user16: /* Linear Search */

2016-12-02T23:32:46Z

‎Linear Search

Proj user16: Created page with "==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..."

2016-12-02T22:21:55Z

Created page with "==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..."

New page

==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'''
<pre>
#include <stdio.h>

/* 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; //setting max size of array as 20
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 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;
}
</pre>

@@ Line 12: / Line 12: @@
 '''Code Snippet'''
-<pre>
+<syntaxhighlight lang="c">
 #include <stdio.h>
@@ Line 50: / Line 50: @@
 	return 0;
+}
-</pre>
+</syntaxhighlight>

@@ Line 20: / Line 20: @@
+{
-	for (int i = 0; i < size; i++                               //looping over the array to find the matching element
+	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
@@ Line 32: / Line 32: @@
 	printf("Enter the size of Array\n");
 	scanf("%d", & size);										// defining the array size
-	int array[size];
+	int* array = (int*)malloc(size*sizeof(int));                //allocating array size dynamically
 	printf("Enter %d values for the array\n",size);

@@ Line 19: / Line 19: @@
 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
+	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
@@ Line 31: / Line 31: @@
 	int  size, key, pos;
 	printf("Enter the size of Array\n");
-	scanf("%d", & size);				                // defining the array size
+	scanf("%d", & size);										// defining the array size
 	int array[size];
@@ Line 37: / Line 37: @@
 	for (int i = 0; i <size; i++)
+	{
-		scanf("%d", & array[i]);				// Setting the array elements
+		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
+	scanf("%d", & key);											// Keying in the value which has to be searched
-	pos = seq_search(key,array,size);				// Calling the Linear search function
+	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
+	if (pos == 0)												// If position of the searching stays at 0 element or beginning
 	printf("Search unsuccessful, element not found in array");
 	else