Exercise 1: The variable middle is defined as an integer. The program contains t
ID: 648552 • Letter: E
Question
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 3: Modify the program to search an array that is in ascending order.
Make sure to alter the array initialization.
// 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;
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
}
Explanation / Answer
#include<iostream>
using namespace std;
int binarySearch(int[], int, int); // function prototype
const int SIZE = 16;
int main()
{
int found, value;
int array[] = { 0, 2, 2, 3, 5, 9, 11, 12, 12, 12, 13, 17, 18, 19, 19, 34 }; // 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
// 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
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.