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

By | June 9, 2015

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:

FC_Binary_Search

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();
}

#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();
}

Screen Shots:

C_program_Binary_Search

C_program_Binary_Search_Output