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 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++ 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 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 |
