Write a Program to Find An Element In An Array Using Linear Search

Find An Element In An Array Using Linear Search

Introduction
In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
Linear search runs in at the worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then the linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely the most practical search algorithm for large lists because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching in most cases.


Algorithm:
LINEAR_SEARCH (ARR,N,NUM)
STEP 1:[INITIALIZE] SET POS=-1
STEP 2:[INITIALIZE] SET I=0
STEP 3:Repeat step 4 WHILE I<N
STEP 4:IF ARR[I]==NUM
               SET POS=I
               PRINT POS
                Goto step 6
                  [END OF LOOP]
                 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


Program to find An element in an ARRAY Using linear search:
#include<stdio.h>
#include<conio.h>
main()
{
int arr[100],num,i,n,found=0,pos=-1;
printf("\n Enter the elements in the array");
scanf("%d",&n);
printf("\n Enter the values of element");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\n Enter the number that has to be searched :");
scanf("%d",&num);
for(i=0;i<n;i++)
{
if(arr[i]==num)
{
found=1;
pos=i;
printf("\n %d is found in the array at position=%d",num,i);
break;
}}
if(found==0)
printf("\n %d does not exist in the array",num);
getch();
}


Output:
1st Case:

2nd Case:

Discussion:

A linear search is the most basic of search algorithm you can have. A linear search sequentially moves through your collection (or data structure) looking for a matching value.

Characteristics:

The worst case performance scenario for a linear search is that it needs to loop through the entire collection; either because the item is the last one, or because the item isn't found. In other words, if you have N items in your collection, the worst case scenario to find an item is N iterations. This is known as O(N) using the Big O Notation. The speed of search grows linearly with the number of items within your collection.

Linear searches don't require the collection to be sorted.

In some cases, you'll know ahead of time that some items will be disproportionally searched for. In such situations, frequently requested items can be kept at the start of the collection. This can result in exceptional performance, regardless of size, for these frequently requested items.