LAB 8.2 Working with the Binar y SearchBring in program binary_search.cpp from the Lab 8 folder. This is SampleProgram 8.2 from the Pre-lab Reading Assignment. The code is the following:// This program demonstrates a Binary Search// PLACE YOUR NAME HERE#include <iostream>using namespace std;int binarySearch(int [], int, int); // function prototypeconst 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 searchedcout << "Enter an integer to search for:" << endl;cin >> value;found = binarySearch(array, SIZE, value);Lesson 8A 151// function call to perform the binary search// on array looking for an occurrence of valueif (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 listint last = numElems - 1; // last element of the listint middle; // variable containing the current// middle value of the listwhile (first <= last){middle = first + (last - first) / 2;if (array[middle] == value)return middle; // if value is in the middle, we are doneelse if (array[middle] < value)last = middle - 1; // toss out the second remaining half of// the array and search the firstelse}first = middle + 1; // toss out the first remaining half of// the array and search the secondreturn -1; // indicates that value is not in the array}152 LESSON 8 Searching and Sorting ArraysExercise 1: The variable middle is defined as an integer. The program containsthe assignment statement middle=first+(last-first)/2. Is the right sideof this statement necessarily an integer in computer memory? Explain howthe middle value is determined by the computer. How does this line ofcode affect the logic of the program? Remember that first, last, andmiddle refer to the array positions, not the values stored in those arraypositions.Exercise 2: Search the array in the program above for 19 and then 12. Recordwhat the output is in each case.Note that both 19 and 12 are repeated in the array. Which occurrence of19 did the search find?Which occurrence of 12 did the search find?Explain the difference.Exercise 3: Modify the program to search an array that is in ascending order.Make sure to alter the array initialization. write the code on your own
LAB 8.2 Working with the Binar y Search
Bring in
Program 8.2 from the Pre-lab Reading Assignment. The code is the following:
// 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);
Lesson 8A 151
// 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; // variable containing the current
// middle value of the list
while (first <= last)
{
middle = first + (last - first) / 2;
if (array[middle] == value)
return middle; // if value is in the middle, we are done
else if (array[middle] < value)
last = middle - 1; // toss out the second remaining half of
// the array and search the first
else
}
first = middle + 1; // toss out the first remaining half of
// the array and search the second
return -1; // indicates that value is not in the array
}
152 LESSON 8 Searching and Sorting Arrays
Exercise 1: The variable middle is defined as an integer. The program contains
the assignment statement middle=first+(last-first)/2. Is the right side
of this statement necessarily an integer in computer memory? Explain how
the middle value is determined by the computer. How does this line of
code affect the logic of the program? Remember that first, last, and
middle refer to the array positions, not the values stored in those array
positions.
Exercise 2: Search the array in the program above for 19 and then 12. Record
what the output is in each case.
Note that both 19 and 12 are repeated in the array. Which occurrence of
19 did the search find?
Which occurrence of 12 did the search find?
Explain the difference.
Exercise 3: Modify the program to search an array that is in ascending order.
Make sure to alter the array initialization.
write the code on your own
Step by step
Solved in 1 steps
