Develop a program to implement the binary search algorithm. This technique compares the search key value with the value of the element that is midway in a "sorted" list. Then:
(a) If they match, the search is over.
(b) If the search key value is less than the middle value, then the first half of the list contains the key value.
(c) If the search keay value is greater than the middle value, then the second half contains the key value.
Repeat this "divide-and-conquer" strategy until we have a match. If the list is reduced to one no-matching element, then the list does not contain the key value. Use sorted list.
#include <stdio.h>
main()
{
int top,bottom,middle,value[50],key,n,i;
clrscr();
printf("Enter the number of elements in array:");
scanf("%d",&n);
printf("Enter the elements of array in ascending order\n");
for(i=1;i<=n;i++)
scanf("%d",&value[i]);
printf("Enter the value which you want to search:");
scanf("%d",&key);
top=n-1;
bottom=0;
do
{
middle=(top+bottom)/2;
if(value[middle]<key)
bottom=middle+1;
else
top=middle;
}
while(top>bottom);
if(top==-1)
printf("List is empty!");
else if(value[top]==key)
printf("value has been found!");
else
printf("Target value has not been found!");
getch();
}
OUTPUT
Enter the number of elements in array: 10
Enter the elements of array in ascending order
1 2 3 4 5 6 7 8 9 11
Enter the value which you want to search: 7
value has been found!
Enter the number of elements in array: 10
Enter the elements of array in ascending order
1 2 3 4 5 6 7 8 9 11
Enter the value which you want to search: 12
Target value has not been found!
(a) If they match, the search is over.
(b) If the search key value is less than the middle value, then the first half of the list contains the key value.
(c) If the search keay value is greater than the middle value, then the second half contains the key value.
Repeat this "divide-and-conquer" strategy until we have a match. If the list is reduced to one no-matching element, then the list does not contain the key value. Use sorted list.
#include <stdio.h>
main()
{
int top,bottom,middle,value[50],key,n,i;
clrscr();
printf("Enter the number of elements in array:");
scanf("%d",&n);
printf("Enter the elements of array in ascending order\n");
for(i=1;i<=n;i++)
scanf("%d",&value[i]);
printf("Enter the value which you want to search:");
scanf("%d",&key);
top=n-1;
bottom=0;
do
{
middle=(top+bottom)/2;
if(value[middle]<key)
bottom=middle+1;
else
top=middle;
}
while(top>bottom);
if(top==-1)
printf("List is empty!");
else if(value[top]==key)
printf("value has been found!");
else
printf("Target value has not been found!");
getch();
}
OUTPUT
Enter the number of elements in array: 10
Enter the elements of array in ascending order
1 2 3 4 5 6 7 8 9 11
Enter the value which you want to search: 7
value has been found!
Enter the number of elements in array: 10
Enter the elements of array in ascending order
1 2 3 4 5 6 7 8 9 11
Enter the value which you want to search: 12
Target value has not been found!