Question

1. // This program demonstrates a Binary Search

   //PLACE YOUR NAME HERE

   #include<iostream>

   using namespace std;

   int binarySearch(int [], int, int);  // function prototype

   const int SIZE = 16;

   int main()

   {

   int found, value;

   int array[] = {34,19,19,18,17,13,12,12,12,11,9,5,3,2,2,0}; // array to be searched

   cout << "Enter an integer to search for:" << endl;

   cin >> value;

   found = binarySearch(array, SIZE, value); //function call to perform the binary search

     //on array looking for an occurrence of value

   if (found == -1)

   cout << "The value " << value << " is not in the list" << endl;

   else

   {

   cout << "The value " << value << " is in position number "

     << found + 1 << " of the list" << endl;

   }

   return 0;

   }

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

   //     binarySearch

   //

   // task:   This searches an array for a particular value

   // data in:     List of values in an orderd array, the number of

   //   elements in the array, and the value searched for

   //   in the array

   // data returned: Position in the array of the value or -1 if value

   //   not found

   //

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

   int binarySearch(int array[],int numElems,int value) //function heading

   {

   int first = 0;     // First element of list

   int last = numElems - 1;     // last element of the list

   int middle; 0   // variable containing the current

     // middle value of the list

   while (first <= last)

   {

   middle = first + (last - first) / 2;

     // write statement to determine if value is in the middle, then we are done

   else if (array[middle]<value)

   last = //what would the last be?   // toss out the second remaining half of

     // the array and search the first

   else

   first = //what would the first be?   // toss out the first remaining half of

     // the array and search the second

   }

   return -1;   // indicates that value is not in the array

   }

Answer 1

Source Code:

Output:

Code in text format (See above images of code for indentation):

/*his program demonstrates a Binary Search*/
/*PLACE YOUR NAME HERE*/
#include<iostream>
using namespace std;
/*function prototype*/
int binarySearch(int [], int, int);
/*size is fixed*/
const int SIZE=16;
/*main function*/
int main()
{
   /*variables*/
   int found, value;
   /*array to be searched*/
   int array[]={34,19,19,18,17,13,12,12,12,11,9,5,3,2,2,0};
   /*read search key from the user*/
   cout << "Enter an integer to search for:" << endl;
   cin >> value;
   /*function call to perform the binary search
   on array looking for an occurrence of value*/
   found = binarySearch(array, SIZE, value);
   /*if value is not found*/
   if (found == -1)
   cout << "The value " << value << " is not in the list" << endl;
   /*if value is found*/
   else
   {
       /*print index*/
   cout << "The value " << value << " is in position number "
   << found + 1 << " of the list" << endl;
   }
   return 0;
}
/*function definition*/
int binarySearch(int array[],int numElems,int value)
{
   /* First element of list*/
   int first=0;
   /* last element of the list*/
   int last=numElems-1;
   /*variable containing the current middle value of the list*/
   int middle=0;   
   while (first<=last)
   {
       /*find middle*/
       middle=first + (last - first) / 2;
       /*if found*/
       if(array[middle]==value)
       {
           /*return index*/
           return middle;
           break;
       }
       /*if value is greater than search first half*/
       else if (array[middle]<value)
           last=middle-1;
       /*else search for last half*/
       else
           first=middle+1;
   }
   /*if not found return -1*/
   return -1;
}