Description:
Binary search is a
vast improvement over the sequential search. For binary
search to work, the
item in the list must be in assorted order. The approach employed in the binary
search is divide and conquer. If the list to be sorted for a specific item is
not sorted, binary search fails.
Program:
#include<stdio.h>
#include<conio.h>
void main()
{
int i,n,key,a[10],low,high,mid;
clrscr();
printf("enter range for array:"); scanf("%d",&n);
printf("enter elements into array:"); for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("the search element:"); scanf("%d",&key);
low=0; high=n-1; for(i=0;i<n;i++)
{
mid=(low+high)/2;
if(a[mid]==key)
{
printf("element %d found at %d",key,mid);
break;
}
if(key<a[mid])
high=mid;
else low=mid+1;
if(i==n-1)
printf("element %d not found in array",key);
}
getch();
}
Output:
enter range for array:4
enter elements into array:12 23 34 45
the search element:45
element 45 found at 4
enter range for array:5
enter elements into array:1 34 56 78 88 the search element:45
element 45 not found in array
Conclusion: the program is error free
More Explanation:
The search always needs to track three values – the midpoint, the first position in the scope and the last position in the scope. With each pass, the algorithm narrows the search scope by half. With each subsequent pass of the data, the algorithm re-calculates the midpoint and searches for the target. First, it searches for the target at the midpoint of the list. It can then determine if the target is in the first half of the list or the second, thus eliminating half of the values. The binary search divides the list into two halves. We should use the binary search on large lists (>50 elements) that are sorted.
VIVA QUESTIONS
1) Define Binary search ?
Ans: Binary search is a vast improvement over the sequential search. For binary search to work, the item in the list must be in assorted order. The approach employed in the binary search is divid and conquer. If the list to be sorted for a specific item is not sorted, binary search fails.
.
Program:
#include<stdio.h>
#include<conio.h>
void main()
{
int i,n,key,a[10],low,high,mid;
clrscr();
printf("enter range for array:"); scanf("%d",&n);
printf("enter elements into array:"); for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("the search element:"); scanf("%d",&key);
low=0; high=n-1; for(i=0;i<n;i++)
{
mid=(low+high)/2;
if(a[mid]==key)
{
printf("element %d found at %d",key,mid);
break;
}
if(key<a[mid])
high=mid;
else low=mid+1;
if(i==n-1)
printf("element %d not found in array",key);
}
getch();
}
Output:
enter range for array:4
enter elements into array:12 23 34 45
the search element:45
element 45 found at 4
enter range for array:5
enter elements into array:1 34 56 78 88 the search element:45
element 45 not found in array
Conclusion: the program is error free
More Explanation:
The search always needs to track three values – the midpoint, the first position in the scope and the last position in the scope. With each pass, the algorithm narrows the search scope by half. With each subsequent pass of the data, the algorithm re-calculates the midpoint and searches for the target. First, it searches for the target at the midpoint of the list. It can then determine if the target is in the first half of the list or the second, thus eliminating half of the values. The binary search divides the list into two halves. We should use the binary search on large lists (>50 elements) that are sorted.
VIVA QUESTIONS
1) Define Binary search ?
Ans: Binary search is a vast improvement over the sequential search. For binary search to work, the item in the list must be in assorted order. The approach employed in the binary search is divid and conquer. If the list to be sorted for a specific item is not sorted, binary search fails.
.
No comments:
Post a Comment