Searching techniques: Linear or Sequential search

There are many applications requiring a search for a particular element. Searching refers to finding out whether a particular element is present in the list. The method that we use for this depends on how the elements of the list are organized. If the list is an unordered list, then we use linear or sequential search, whereas if the list is an ordered list, then we use binary search.
 
The search proceeds by sequentially comparing the key with elements in the list, and continues until either we find a match or the end of the list is encountered. If we find a match, the search terminates successfully by returning the index of the element in the list which has matched. If the end of the list is encountered without a match, the search terminates unsuccessfully.

Example

#include <stdio.h>
#define MAX 10
void lsearch(int list[],int n,int element)
{
   int i, flag = 0;
   for(i=0;i<n;i++)
   if( list[i] == element)
   {
      printf(" The element whose value is %d is present at position %d in list\n", element,i);
      flag =1;
      break;
   }
   if( flag == 0)
       printf("The element whose value is %d is not present in the list\n",element);
}

void readlist(int list[],int n)
{
   int i;
   printf("Enter the elements\n");
   for(i=0;i<n;i++)
       scanf("%d",&list[i]);
}

void printlist(int list[],int n)
{
   int i;
   printf("The elements of the list are: \n");
   for(i=0;i<n;i++)
       printf("%d\t",list[i]);
}
int main()
{
   int list[MAX], n, element;
   printf("Enter the number of elements in the list max = 10\n");
   scanf("%d",&n);
   readlist(list,n);
   printf("\nThe list before sorting is:\n");
   printlist(list,n);
   printf("\nEnter the element to be searched\n");
   scanf("%d",&element);
   lsearch(list,n,element);
   getchar();
   return 0;
}

Explanation

• In the best case, the search procedure terminates after one comparison only, whereas in the worst case, it will do n comparisons.
• On average, it will do approximately n/2 comparisons, since the search time is proportional to the number of comparisons required to be performed.
• The linear search requires an average time proportional to O(n) to search one element. Therefore to search n elements, it requires a time proportional to O(n2).
• We conclude that this searching technique is preferable when the value of n is small. The reason for this is the difference between n and n2 is small for smaller values of n.