Difference between revisions of "Linear Search"
(→Linear Search) |
Proj user16 (talk | contribs) |
||
| Line 19: | Line 19: | ||
int seq_search(int key, int array[], int size) | int seq_search(int key, int array[], int size) | ||
{ | { | ||
| − | + | ||
| − | for (int i = 0; i < size; i++ | + | 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 | if(array[i] == key) return i + 1; //returning the position of the matched element | ||
| Line 31: | Line 31: | ||
int size, key, pos; | int size, key, pos; | ||
printf("Enter the size of Array\n"); | printf("Enter the size of Array\n"); | ||
| − | scanf("%d", & size); | + | scanf("%d", & size); // defining the array size |
int array[size]; | int array[size]; | ||
| Line 37: | Line 37: | ||
for (int i = 0; i <size; i++) | for (int i = 0; i <size; i++) | ||
{ | { | ||
| − | scanf("%d", & array[i]); | + | scanf("%d", & array[i]); // Setting the array elements |
} | } | ||
printf("Enter the key to be searched\n"); | printf("Enter the key to be searched\n"); | ||
| − | scanf("%d", & key); | + | scanf("%d", & key); // Keying in the value which has to be searched |
| − | pos = seq_search(key,array,size); | + | pos = seq_search(key,array,size); // Calling the Linear search function |
| − | if (pos == 0) | + | if (pos == 0) // If position of the searching stays at 0 element or beginning |
printf("Search unsuccessful, element not found in array"); | printf("Search unsuccessful, element not found in array"); | ||
else | else | ||
Revision as of 08:21, 7 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;
}
