Design an algorithm, draw a corresponding flow chart and write a ‘C’ program for Binary Search, to search a given number among the list of numbers. 10m Dec2007
Algorithm
Step 1: Declare an array ‘k’ of size ‘n’ i.e. k(n) is an array which stores all the keys of a file containing ‘n’ records
Step 2: I <– 0
Step 3: low<–0, high <– n-1
Step 4: while (low <= high)do
mid = (low + high)/2
if (key=k[mid]) then
write “record is at position”, mid+1 //as the array starts from the 0th position
else
if(key < k[mid]) then
high = mid – 1
else
low = mid + 1
endif
endif
endwhile
Step 5: Write “Sorry, key value not found”
Step 6: Stop
FlowChart:
Program Binary Search:-
#include<stdio.h>
void main()
{
int NUM[10]={0,1,2,3,4,5,6,7,8,9};
int LOW=0,HIGH=9,KEY,MID,FLAG=0;
clrscr();
printf(“ENTER KEY NUMBERS BTWN (0-9)\n”);
scanf(“%d”,&KEY);
do
{
MID=(LOW+HIGH)/2;
if(KEY==NUM[MID])
{
printf(“\nKEY FOUND AT %d POSITION\n”,MID+1);
FLAG=1;
}
else
{
if(KEY<NUM[MID])
HIGH=MID-1;
else
LOW=MID+1;
}
}while(LOW <= HIGH && FLAG == 0);
if(FLAG == 0)
printf(“\nSORRY KEY VALUE NOT FOUND\n”);
getch();
}
[codesyntax lang=”c”]
#include<stdio.h>
void main()
{
int NUM[10]={0,1,2,3,4,5,6,7,8,9};
int LOW=0,HIGH=9,KEY,MID,FLAG=0;
clrscr();
printf(“ENTER KEY NUMBERS BTWN (0-9)\n”);
scanf(“%d”,&KEY);
do
{
MID=(LOW+HIGH)/2;
if(KEY==NUM[MID])
{
printf(“\nKEY FOUND AT %d POSITION\n”,MID+1);
FLAG=1;
}
else
{
if(KEY<NUM[MID])
HIGH=MID-1;
else
LOW=MID+1;
}
}while(LOW <= HIGH && FLAG == 0);
if(FLAG == 0)
printf(“\nSORRY KEY VALUE NOT FOUND\n”);
getch();
}
[/codesyntax]
Screen Shots:
