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: #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; // 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 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 } Exercise 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.
LAB 8.2 Working with the Binar y Search
Bring in program binary_search.cpp from the Lab 8 folder. This is Sample
Program 8.2 from the Pre-lab Reading Assignment. The code is the following:
#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; // 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
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
}
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.
Trending now
This is a popular solution!
Step by step
Solved in 1 steps
