Searching Methods :
1. linear or sequential search .
2. Binary search .
1. Linear search /Sequential search :
This is a simplex method of searching It is also called as a linear search and applied to sequential storage structure like file array or linked list.
ANALYSIS OF LINEAR SEARCH :
BEST CASE :
The best case occurs when the key is found at the first position. i . e. at index 0 here only one comparison performed Hence the best time complexity is omega 1.
WORST CASE :
This case occurs when the key is found in the array in such a case n comparisons are performed Hence the ort case time complexity is O(n).
AVERAGE CASE :
Let us consider that all keys occurs with equal probability for all keys Ki (0 <= i<n) the total number of comparisons for successful searches are :
1 + 2 + . . . . . + n = n(n+1) /2
so average comparison is = n(n+1)/2n = (n+1 ) /2 Hence the average case time complexity of this method is O(n).
EFFICIENCY OF LINEAR SEARCHES ARE :
BEST CASE : OMEGA 1 .
WORST CASE : O(n).
AVERAGE CASE : O(n).
Advantages :
1. It is a very simple method .
2. It does not require the data to be ordered.
3. It does not require any additional data structure.
Disadvantage :
1. If n is very large this method is very inefficient and slow.
2. its worst case complexity is O(n) Hence the worst case search time increase in proportion to the number of elements.
FUNCTION FOR LINEAR SEARCH :
The function for linear search accepts an array , number of element and key as arguments it return the position of of key is found and return -1 if key is not found.
int linear_ search (int A[], int n, int key)
{
int i ;
for (i = 0 ; i < n ; i ++)
if (A[ i ] = = key )
return 1; /// return position
return -1 ; ///key not found
}
Program for linear / sequential search :
#include<stdio.h>
#include<stdlib.h>
int compcount=0;
int linearsearch(int a[],int n, int key)
{
int i;
for(i=0;i<n;i++)
{
compcount++;
if(a[i] ==key)
return 1;
}
return -1;
}
void accept(int a[],int n)
{
int i;
printf("enetr the %d element :",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
}
void main()
{
int a[30],pos,key,n;
printf("how many number you wnat in an array:");
scanf("%d",&n);
accept(a,n);
printf("enetr number to be searched :");
scanf("%d",&key);
pos = linearsearch(a,n,key);
if(pos==-1)
printf("%d not found in the array ",key);
else
printf("\n %d found at position : ",pos);
printf("\nthe total number of comparision =%d",compcount);
}
2. Binary Search :
This method is based on divide an conquer algorithmic strategy. in this strategy problem is solved by dividing the set of element and performing operation on each part
Precondition for binary search:
1. Data must be organized in linear way.
2. Data has to be in the sorted order in either ascending or descending order.
Procedure :
* In this method the list is partitioned in two equal halves.
* The key compared with the middle element If a match is found the search is terminate.
* If the key is less than middle element search proceed in the same manner in the upper half of the table.
* if the key is greater than middle element search proceed in the same way in the lower half of the table.
* The process continues till the key is found or no more partition are possible.
* Thus every time a match is not found the remaining list sized to searched reduce to half .
EFFICIENCY :
BEST CASE :
In this best case key is found at the middle position after 1 comparison . Hence the best case time complexity is omega 1
WORST CASE :
If we observe the loop is repeatedly halving the number off element. Hence the algorithm complexity is logarithmic. Thus the time complexity is O(log2 n) which is very efficient.
ADVANTAGE :
Worst case time complexity is O (log2n) which is very efficient compared to sequential search (O(n)).
DISADVANTAGE :
Data has to be in sorted order.
Difference between linear search and binary search .
* FUNCCTION FOR BINARY SEARCH :
int binarysearch( int A[],int n ,int key )
{
int begin = 0, middle, end = n- 1;
while (begin < = end )
{
mid = (begin + end )/2;
if (key == A[mid]
return mid ;
if (key < A[mid ])
end = mid -1 ;
else
begin = mid +1 ;
}
return -1;
}
* program for Binary search :
#include<stdio.h>
#include<stdlib.h>
int binarysearch(int a[],int n,int key)
{
int begin=0,end=n-1,mid;
if(begin<=end)
{
mid=(begin+end)/2;
if(key == a[mid])
return mid;
if(key <= a[mid])
end=mid-1;
else
begin=mid+1;
}
else
{
return -1;
}
}
void accept(int a[],int n)
{
int i;
printf("enter numbers in an array :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
}
int main()
{
int n,key,a[30];
int pos;
printf("enter how many numbers you want in an array :");
scanf("%d",&n);
accept(a,n);
printf("enter number i to be search :");
scanf("%d",&key);
pos = binarysearch(a,n,key);
if(pos == -1)
printf("key is not found ");
else
printf("key is found ");
}
0 comments:
Post a Comment