SEARCHING
Searching is an operation of
data structure to search an item in a list. There are 3 types of searching
methods:- Linear search, Binary search, Hashing .
Linear Search:-
In this method the item
search in a sequential order starting from 0 index and stop until the last
index or the item found.
WAP to search an item using linear search.
#include<stdio.h>
#define MAX 20
int lsearch(int[],int,int);
void main()
{ int a[MAX],n,item,i;
printf("\nEnter number of
element in array:");
scanf("%d",&n);
printf("\nEnter %d
elements:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the search
item:");
scanf("%d",&item);
i=lsearch(a,n,item);
if(i>=0)
printf("\n%d is at index
number %d",item,i);
else
printf("\n%d is not
found",item);
return 0;
}
int lsearch(int a[],int n,int item)
{ int i;
for(i=0;i<n;i++)
{
if(a[i]==item)
return
i;
}
return -1;
}
Binary Search
ž Binary
search algorithm assumes that the items in the list being searched are sorted.
ž The
algorithm begins at the middle of the list in a binary search.
ž We
compare between the search item and the middle element of the array. If match
return the index number.
ž If
the item for which we are searching is less than the item in the middle, we
know that the item won’t be in the second half of the list. If the item for which we are searching is
greater than the item in the middle, we know that the item won’t be in the
first half of the list.
ž The
process continues with each comparison cutting in half the portion of the list
where the item might be.
ž The
time complexity of this algorithm is O(log n)
Algorithm to Binary Search
BSearch(A,n,item)
Step 1:- Set low=0
Set
high=n-1;
Step 2:- Repeat step 3 to 9 until low<=high
Step 3:- Set mid=(low+high)/2
Step 4:- if (item== A[mid] ) then
Step 5:- return mid
Step 6:- else if( item < A[mid] ) then
Step 7:- high=mid -1
Step 8:- else
Step 9:- low=mid
+ 1
[End
if]
[End loop]
Step 10:- return -1
Step 11:- End
WAP to search an item in a sorted list using binary search.
#include<stdio.h>
#define MAX 20
int bsearch(int[],int,int);
void main()
{
int a[MAX],n,item,i;
printf("\nEnter number of
element in array:");
scanf("%d",&n);
printf("\nEnter %d
elements:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the search
item:");
scanf("%d",&item);
i=bsearch(a,n,item);
if(i>=0)
printf("\n%d is at index
number %d",item,i);
else
printf("\n%d is
not found",item);
}
int bsearch(int a[],int n,int item)
{ int l,u,m;
l=0;u=n-1;
while(l<=u)
{ m=(l+u)/2;
if(item==a[m])
return
m;
else
if(item<a[m])
u=m-1;
else
l=m+1;
}
return -1;
}
