Linear Search Algorithm

 What is Search?

Search is a process of finding a value in a list of values. In other words, searching is the process of locating given value position in a list of values.

Linear Search Algorithm (Sequential Search Algorithm)

Linear search algorithm finds a given element in a list of elements with O(n) time complexity where n is total number of elements in the list. This search process starts comparing search element with the first element in the list. If both are matched then result is element found otherwise search element is compared with the next element in the list. Repeat the same until search element is compared with the last element in the list, if that last element also doesn't match, then the result is "Element not found in the list". That means, the search element is compared with element by element in the list.

Linear search is implemented using following steps...

  • Step 1 - Read the search element from the user.
  • Step 2 - Compare the search element with the first element in the list.
  • Step 3 - If both are matched, then display "Given element is found!!!" and terminate the function
  • Step 4 - If both are not matched, then compare search element with the next element in the list.
  • Step 5 - Repeat steps 3 and 4 until search element is compared with last element in the list.
  • Step 6 - If last element in the list also doesn't match, then display "Element is not found!!!" and terminate the function.

Example

Consider the following list of elements and the element to be searched...



Algorithm
 
  • LINEAR_SEARCH(A, N, VAL)
  • Step 1: [INITIALIZE] SET POS = -1
  • Step 2: [INITIALIZE] SET I = 1
  • Step 3: Repeat Step 4 while I<=N
  • Step 4: IF A[I] = VAL
    SET POS = I
    PRINT POS
    Go to Step 6
    [END OF IF]
    SET I = I + 1
    [END OF LOOP]
  • Step 5: IF POS = -1
    PRINT " VALUE IS NOT PRESENT IN THE ARRAY "
    [END OF IF]
  • Step 6: EXIT
 Implementation of Linear Search Algorithm using C Programming Language
 
#include<stdio.h>
#include<conio.h>

void main(){
  int list[20],size,i,item;

  printf("Enter size of the list: ");
  scanf("%d",&size);

  printf("Enter any %d integer values: ",size);
  for(i = 0; i < size; i++)
    scanf("%d",&list[i]);

  printf("Enter the element to be Search: ");
  scanf("%d",&item);
  
  // Linear Search Logic
  for(i = 0; i < size; i++)
  {
     if(item == list[i])
     {
        printf("Element is found at %d index", i);
        break;
     }
  }
  if(i == size)
     printf("Given element is not found in the list!!!");
  getch();
}
 

Output 

 

 

 

No comments:

Post a Comment