Difference between revisions of "Linear Search"
Proj user16 (talk | contribs) (→Linear Search) |
Proj user16 (talk | contribs) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 12: | Line 12: | ||
'''Code Snippet''' | '''Code Snippet''' | ||
| − | < | + | <syntaxhighlight lang="c"> |
#include <stdio.h> | #include <stdio.h> | ||
| 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 | + | int* array = (int*)malloc(size*sizeof(int)); //allocating array size dynamically |
printf("Enter %d values for the array\n",size); | printf("Enter %d values for the array\n",size); | ||
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 | ||
| Line 50: | Line 50: | ||
return 0; | return 0; | ||
} | } | ||
| − | </ | + | </syntaxhighlight> |
Latest revision as of 22:55, 8 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 = (int*)malloc(size*sizeof(int)); //allocating array size dynamically
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;
}
