Question

Let bottom be the subscript of the initial array element. 

2. Let top be the subscript of the last array element. 

3. Let found be false. 

4. Repeat as long as bottom isn’t greater than top and the target has not been found 

    5. Let middle be the subscript of the element halfway between bottom and top. 

    6. if the element at middle is the target 

        7. Set found to true and index to middle. else if the element at middle is larger             than the target

        8. Let top be middle − 1. 

    else 

        9. Let bottom be middle + 1. 

Write a program that consists of a function named binary_srch that implements this algorithm; and a main() program that call the function to search for a target in an array with a large number of integers (for instance, of the order of hundred). The elements of the array are assumed to be in order. The function prototype should be

int binary_srch(const int search_array[], int target, int size); 

where search_array is the array to search for, target is the searched element and size is the size of the array. 

Rules: 

    •In your program, you should use the following macros: 

#define SIZE_OF_ARRAY 10 

#define TRUE 1 

#define FALSE 0 

#define NOT_FOUND -1 

    •You should use the following variables in the variables declaration part of your function definition: 

int top, bottom, middle, index, found; 

bottom = 0; 

top = size - 1; 

found = FALSE;

Answer 1

Program Plan:

• Declare a prototype for the function BinarySearch of user defined function.

• Define the main() function.

o Declare the required variables.

o Prompt the user to enter the size of the array.

o Read the size of the array into variable n.

o Prompt the user to enter the elements.

o Read the elements into the array.

o Check whether the elements entered are in ascending order.

• If the elements in the array are in ascending order, prompt the user to enter the search element.

• Call the BinarySearch function by passing array, its size and the search key.

• Define BinarySearch function.

o Declare the required variables.

o Use a loop to search the element in the array.

o The logic should frist point to the middle element, then check the conditions, whether the search value lies below the middle term or above the middle term.

• If the middle term itself is a search value set the flag value to true.

• If the seach element is below the mid term, then search the value inbetween the frist term and middle term.

• If the seach element is above the mid term, then search the value inbetween the middle+1 term to last term.

o Next, check for the flag value.

• If the flag value is true, display the message that the element is found and its position value.

• If the flag value is false, display the message that the element is not found.

Program:

#include

#include

Declare the prototype of inarySearchfunction:

void BinarySearch(int a[],int n,int key);

In main() function:

{

/*declaration and initialization*/

int a[10], i, n, key, flag=0;

clrscr();/*clear the screen*/

Prompt user to enter the size of the array using printf() statement. Read input from user using scanf() statement.

/*for()loop is used to initialize value from 0-(n-1)*/

for(i=0;i<n;i++)< p="">

{

/*prompt user to enter element*/

printf("Enter element[%d]:",i);

scanf("%d", &a[i]); /*scan input*/

}

Prompt user to enter array elements in ascending order. Use for() loop to initialize values from 0-(n-1).Inside for() loop a printf() statement is used to prompt user to enter elements. Use scanf() to read input from user.

/*check the input array a[] is sorted*/

for(i=1;i<n;i++)< p="">

{

/*if a[] is not sorted in ascending order*/

if(a[i]<a[i-1])< p="">

{

/*print message to user*/

printf("Given input is not sorted\n");

flag = 1; /*set the flag value*/

break; /*break the execution*/

}

}

Check whether the input element is in ascending order or not. Use for() loop to initialize values from 0-(n-1).

Inside the for() loop an if() statement is used to compare the consecutive elements. If the previous element is greater than current element then the input elements not in sorted order, then set the flag value to 1, show message that input array elements are not in increasing order, and break the execution of loop.

for(i=1;i<n;i++)< p="">

{

/*if a[] is not sorted in ascending order*/

if(a[i]<a[i-1])< p="">

{

/*print message to user*/

printf("Given input is not sorted\n");

flag = 1; /*set the flag value*/

break; /*break the execution*/

}

}

Check the flag value:

If flag=0, prompt the user to enter key value using printf() statement. Scan input from user using scanf() statement, and call user-defined function by passing three integers arguments, array a[], number of elements n and element to search key.

if(flag==0)

{

/*prompt user to enter a key value to search*/

printf("Enter key to search:");

scanf("%d",&key); /*scan input from user*/

/*call user-defined function by passing three

Arguments a is the array, n is the number of

elements, key is the key value to be search in the array*/

BinarySearch(a,n,key);

}

getch();

}

Definition of user-defined function:

void BinarySearch(int a[],int n,int key)

{

Declare and initilize variables:

/*declaration and initialization*/

int bottom=0,top=(n-1),middle, pos, found=0;

Logic: [top, bottom] denotes the range in which element. Initially bottom = 0, top = (n-1), which covers range. In every step reduce the range by doing the following steps:

1. If the middle element (middle) is greater than key then set bottom = (middle+1) range [middle+1 , top]

2. If middle element is the key, then store the position and set found = 1(true).

3. If the middle element is less than key then set top = middle-1 range[bottom,middle-1].

while(bottom<top)< p="">

{

/*find the middle element*/

middle=(bottom+top)/2;

/*if the key is less than a[middle]*/

if(a[middle]< key)

{

/*set bottom = middle+1*/

bottom = middle +1;

}

/*if the middle element is the key*/

else if(a[middle] == key)

{

/*assign the position of

element in 'pos' variable*/

pos = middle;

found = 1; /*set found=1*/

break;/*break the execution*/

}

/*if the key is greater than a[middle]*/

else

{

top = middle-1;/*set top = middle-1*/

}

}

Check the found value:

• If found=0, then print a message to user that number is not found.

• If found=1, then print a message that the element is found with their position.

/*check the found*/

if(found==0)

/*if found==0 then show not message*/

printf("Number not found");

else

/*else() part will execute when found==1*

show message that number found with their

position*/

printf("Number found at position:%d",pos+1);

}

Program Code:

/**********************************************************

*Program for Binary search using user-defined function. *

**********************************************************/

#include

#include

/*prototype of user-defined function*/

void BinarySearch(int a[],int n,int key);

void main()

{

/*declaration and initialization*/

int a[10], i, n, key, flag=0;

clrscr();/*clear the screen*/

/*prompt user to enter the size of an array which is

less than 10*/

printf("Enter the size of an array(<10):");

scanf("%d", &n);/*read input from user*/

/*prompt user to enter element in ascending order*/

printf("Enter the elements in ascending order:\n");

/*for()loop is used to initialize value from 0-(n-1)*/

for(i=0; i<n; i++)<="" p="">

{

/*prompt user to enter element*/

printf("Enter element[%d]:",i);

scanf("%d", &a[i]); /*scan input*/

}

/*check the input array a[] is sorted*/

for(i=1; i<n; i++)<="" p="">

{

/*if a[] is not sorted in ascending order*/

if(a[i]<a[i-1])< p="">

{

/*print message to user*/

printf("Given input is not sorted\n");

flag = 1; /*set the flag value*/

break; /*break the execution*/

}

}

/*check the flag value, if it is 0 if() loop will

execute*/

if(flag==0)

{

/*prompt user to enter a key value to search*/

printf("Enter key to search:");

/*scan input from user*/

scanf("%d",&key);

/*call BinarySearch function*/

BinarySearch(a,n,key);

}

getch();

}

/*definition of user-defined function*/

void BinarySearch(int a[],int n, int key)

{

/*declaration and initialization*/

int bottom=0,top=(n-1),middle, pos, found=0;

while(bottom<top)< p="">

{

/*find the middle element*/

middle=(bottom+top)/2;

/*if the key is less than a[middle]*/

if(a[middle]< key)

{

/*set bottom = middle+1*/

bottom = middle +1;

}

/*if the middle element is the key*/

else if(a[middle] == key)

{

/*assign the position of

element in 'pos' variable*/

pos = middle;

found = 1; /*set found=1*/

break;/*break the execution*/

}

/*if the key is greater than a[middle]*/

else

{

top = middle-1;/*set top = middle-1*/

}

}

/*check the found*/

if(found==0)

/*if found==0 then show not message*/

printf("Number not found");

else

/*else() part will execute when found==1*

show message that number found with their

position*/

printf("Number found at position:%d",pos+1);

}

Sample output:

1) Enter the size of an array(<10):5

Enter the elements in asscending order

Enter element[0]:4

Enter element[1]:7

Enter element[2]:9

Enter element[3]:12

Enter element[5]:15

Enter key to search:9

Number found at position:3

2) Enter the size of an array(<10):4

Enter the elements in asscending order

Enter element[0]:2

Enter element[1]:7

Enter element[2]:9

Enter element[3]:10

Enter key to search:15

Number not found

3) Enter the size of an array(<10):5

Enter the elements in asscending order

Enter element[0]:4

Enter element[1]:7

Enter element[2]:1

Enter element[3]:12

Enter element[5]:15

Given input is not sorted