#include <iostream> using namespace std; int binarySearch(int [], int, int); //
ID: 3903506 • Letter: #
Question
#include <iostream>
using namespace std;
int binarySearch(int [], int, int); // function prototype
const int SIZE = 16;
int main()
{
int found, value;
int list[] = {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(list, 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;
}
system ("pause");
return 0;
}
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 half of the array
//and search the first
else
first = middle + 1; // toss out the first half of the array
//and search the second
}
return -1; // indicates that value is not in the array
}
Add code to output the number of lookups (i.e. search comparisons) the program
performs. Show the results for the following sample test data: 19, 13, 2, 55.
Explanation / Answer
#include <iostream>
using namespace std;
int binarySearch(int[], int, int); // function prototype
const int SIZE = 16;
int main()
{
int found, value;
int list[] = {
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: ";
cin >> value;
found = binarySearch(
list, 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;
}
system("pause");
return 0;
}
int binarySearch(int array[], int numElems, int value) // function heading
{
int count = 0; // to keep track of # of comparisions
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)
{
// incrementing count by 1 every time a comparision takes place
count++;
middle = first + (last - first) / 2;
if (array[middle] == value)
{
// printing comparisions before returning value
cout << "Number of comparisions are " << count << endl;
return middle; // if value is in the middle, we are done
}
else if (array[middle] < value)
last = middle - 1; // toss out the second half of the array
// and search the first
else
first = middle + 1; // toss out the first half of the array
// and search the second
}
// printing comparisions before returning value
cout << "Number of comparisions are " << count << endl;
return -1; // indicates that value is not in the array
}
/*SAMPLE OUTPUT
Enter an integer to search for: 19
Number of comparisions are 3
The value 19 is in position number 2 of the list
Enter an integer to search for: 13
Number of comparisions are 3
The value 13 is in position number 6 of the list
Enter an integer to search for: 2
Number of comparisions are 3
The value 2 is in position number 14 of the list
Enter an integer to search for: 55
Number of comparisions are 4
The value 55 is not in the list
*/
#include <iostream>
using namespace std;
int binarySearch(int[], int, int); // function prototype
const int SIZE = 16;
int main()
{
int found, value;
int list[] = {
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: ";
cin >> value;
found = binarySearch(
list, 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;
}
system("pause");
return 0;
}
int binarySearch(int array[], int numElems, int value) // function heading
{
int count = 0; // to keep track of # of comparisions
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)
{
// incrementing count by 1 every time a comparision takes place
count++;
middle = first + (last - first) / 2;
if (array[middle] == value)
{
// printing comparisions before returning value
cout << "Number of comparisions are " << count << endl;
return middle; // if value is in the middle, we are done
}
else if (array[middle] < value)
last = middle - 1; // toss out the second half of the array
// and search the first
else
first = middle + 1; // toss out the first half of the array
// and search the second
}
// printing comparisions before returning value
cout << "Number of comparisions are " << count << endl;
return -1; // indicates that value is not in the array
}
/*SAMPLE OUTPUT
Enter an integer to search for: 19
Number of comparisions are 3
The value 19 is in position number 2 of the list
Enter an integer to search for: 13
Number of comparisions are 3
The value 13 is in position number 6 of the list
Enter an integer to search for: 2
Number of comparisions are 3
The value 2 is in position number 14 of the list
Enter an integer to search for: 55
Number of comparisions are 4
The value 55 is not in the list
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.