Linear Search/Sequential Search in C, C++, Python, Java , Php


C Implementation Of Linear Search    , C++ Implementation Of Linear Search    , Python Implementation Of Linear Search    , Java Implementation Of Linear Search    , PHP Implementation Of Linear Search


Linear Search/Sequential Search in C, C++, Python, Java , Php

The simplest search technique is the sequential search. In this technique we start at the beginning of the list / array / table / file and search for the desired element by matching the value with each record being traversed, the process is continued till either the desired record is found or list is completely traversed.

This technique is suitable for a table which is arranged in the form of an array or linked list. This search may be improved if the list is ordered / sorted.

Advantages and disadvantages of Linear search

Advantages:

  • The linear search is simple
  • It is very easy to understand and implement
  • It does not require the data in the array to be sorted in any particular order.
  • It is memory efficient.

 Disadvantages

  • The linear search in inefficient.
  • It is slower
  • It needs more space and time complexity.

Algorithm

Case: 1
When the array elements are not sorted

Sequential_search(A,N,NUM)
A: Array containing elements (unsorted)
N: Total number of elements
NUM: element to search

Step no Process
1.   Set i=0
2.    Repeat steps 3,4 while (i<N)
3     If(A[i]=NUM) then
        Display “Element is present”
        Goto step 6
        [end of if block]
4   Set i=i+1
5   Display “Element is not present”
6   Return

Algorithm
Case:2
When the array elements are sorted

Sequential_search(A,N,NUM)
A: Array containing elements (sorted)
N: Total number of elements
NUM: element to search
Step no Process
1.   Set i=0
2.   Repeat steps 3,4 and 5 while (i<N)
3    If (A[i]>NUM) then
      Goto step 6
      [end of if block]
4    If(A[i]=NUM) then
      Display “Element is present”
      Goto step 7
      [end of if block]
5   Set i=i+1
6    Display “Element is not present”
7   Return

The complexity of the search algorithm is given by the number of comparisons between the element to search and the array elements.

Best Case :

The desired element is present in the first position of the array, i.e. only one comparison is made. So c(n)=O(1)

Worst case:

The worst case occurs when the element to search is the last element in the array or it is not present in the array. Then the number of comparisons will be “n” so the complexity is order of n i.e. O(n).

Average Case:

If the element to search is present ,then it is possible that it may be present at any location, so the of comparisons can be any of the following

1,2,3,4.. . . . n and each number occurs with the probability p=1/n

So

Total number of comparisons amount to

 C(n)=1/n + 2/n + 3/n + . . . . n/n

 = (1+2+3+ . . . +n)* 1/n

=n*(n+1)/2 * 1/n

= (n+1)/2

 Thus the average number of comparisons needed to find an element is approximately equal to half the number of elements in the array.

C Linear Search

C Implementation Of Linear Search

 /* sequential search or linear search */
#include<stdio.h>
#include<conio.h>
void main()
{
int a[30],i,n,m,pos=0;
clrscr();
printf(“Enter the total number of elements “);
scanf(“%d”,&m);
printf(“enter the array elements \n”);
for(i=0;i<m;i++)
{
printf(“enter the %d element “,i);
scanf(“%d”,&a[i]);
}
printf(“enter the value of the element to search “);
scanf(“%d”,&n);
for(i=0;i<m;i++)
{
if (n==a[i])
{
pos=i+1;
break;
}
}
if (pos>0)
printf(“the element is found at %d position \n”,pos);
else
printf(“element to be searched is not found\n”);
getch();
} 

C++ Linear Search

C++ Implementation Of Linear Search

 /* sequential search or linear search
and print position */
#include<iostream.h>
#include<conio.h>
int lsearch(int a[],int n,int n1);
void main()
{
int a[30],i,n,n1,pos;
clrscr();
cout<<“Enter the total number of elements “;
cin>>n;
for(i=0;i<n;i++)
{
cout<<“enter the element “;
cin>>a[i];
}
cout<<“enter the element to search “;
cin>>n1;
pos=lsearch(a,n,n1);
if (pos==-1)
cout<<“Element is not present”<<endl;
else
cout<<“Element found at location “<<pos+1<<endl;
getch();
}
int lsearch(int a[],int n,int n1)
{
int i;
for(i=0;i<n;i++)
{
if (a[i]==n1)
{
return(i);
}
}
return(-1);
} 

Python Linear Search

Python Implementation Of Linear Search

#sequential search
def linear_search(n1, num):
    """Return index if element is found
        else -1 is returned"""
    for i in range(len(n1)):
        if (n1[i] == num):
            return i
    return -1
#enter numbers as
#Enter the list of numbers: 3 4 5 6 7 8
n = input('Enter the list of numbers: ')
n1 = n.split()
#convert all elements to int
n1 = [int(x) for x in n1]
num = int(input('The number to search for: '))
index = linear_search(n1, num)
if(index < 0):
    print('{} was not found.'.format(num))
else:
    print('{} was found at index {}.'.format(num, index))

Output:

Enter the list of numbers: 23 6 5 4
The number to search for: 6
6 was found at index 1.
>>>


C Implementation Of Linear Search    , C++ Implementation Of Linear Search    , Python Implementation Of Linear Search    , Java Implementation Of Linear Search    , PHP Implementation Of Linear Search


Tutorials

Technical Questions

Interview Questions

C Programming
C++ Programming
Class 11 (Python)
Class 12 (Python)
C Language
C++ Programming
Python

C Interview Questions
C++ Interview Questions
C Programs
C++ Programs

Leave a Reply

Your email address will not be published. Required fields are marked *

Number Of Visitors

0270406