Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive function BinarySearch() with the following specifications: Parameters: a target integer a vector of integers lower and upper bounds within which the recursive call will search Return value: the index within the vector where the target is located -1 if target is not found The template provides the main program and a helper function that reads a vector from input. The algorithm begins by choosing an index midway between the lower and upper bounds. If target == integers.at(index) return index If lower == upper, return -1 to indicate not found Otherwise call the function recursively on half the vector parameter: If integers.at(index) < target, search the vector from index + 1 to upper If integers.at(index) > target, search the vector from lower to index - 1 The vector must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to BinarySearch(): Count the number of calls to BinarySearch(). Count the number of times when the target is compared to an element of the vector. Note: lower == upper should not be counted. Hint: Use a global variable to count calls and comparisons. The input of the program consists of: the number of integers in the vector the integers in the vector the target to be located Ex: If the input is: 9 1 2 3 4 5 6 7 8 9 2 the output is: index: 1, recursions: 2, comparisons: 3 ***COULD YOU DEBUG THE CODE. I INCLUDED THE OUTPUT IMAGES SO YOU CAN SEE WHERE IT DIFFERES*** #include #include #include
15.14 LAB: Binary search
Binary search can be implemented as a recursive
Complete the recursive function BinarySearch() with the following specifications:
- Parameters:
- a target integer
- a vector of integers
- lower and upper bounds within which the recursive call will search
- Return value:
- the index within the vector where the target is located
- -1 if target is not found
The template provides the main program and a helper function that reads a vector from input.
The algorithm begins by choosing an index midway between the lower and upper bounds.
- If target == integers.at(index) return index
- If lower == upper, return -1 to indicate not found
- Otherwise call the function recursively on half the vector parameter:
- If integers.at(index) < target, search the vector from index + 1 to upper
- If integers.at(index) > target, search the vector from lower to index - 1
The vector must be ordered, but duplicates are allowed.
Once the search algorithm works correctly, add the following to BinarySearch():
- Count the number of calls to BinarySearch().
- Count the number of times when the target is compared to an element of the vector. Note: lower == upper should not be counted.
Hint: Use a global variable to count calls and comparisons.
The input of the program consists of:
- the number of integers in the vector
- the integers in the vector
- the target to be located
Ex: If the input is:
9 1 2 3 4 5 6 7 8 9 2the output is:
index: 1, recursions: 2, comparisons: 3***COULD YOU DEBUG THE CODE. I INCLUDED THE OUTPUT IMAGES SO YOU CAN SEE WHERE IT DIFFERES***
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int recursions = 0;
int comparisions = 0;// Read integers from input and store them in a vector.
// Return the vector.
vector<int> ReadIntegers() {
int size;
cin >> size;
vector<int> integers(size);
for (int i = 0; i < size; ++i) { // Read the numbers
cin >> integers.at(i);
}
sort(integers.begin(), integers.end());
return integers;
}
int BinarySearch(int target, vector<int> integers, int lower, int upper) {
recursions++;
if (lower > upper)
{
return -1;
}
int mid = (lower + upper) / 2;
if (integers[mid] == target)
{
comparisions++;
return mid;
}
else if (integers[mid] > target)
{
comparisions += 2;
return BinarySearch(target, integers, lower, mid - 1);
}
else
{
comparisions += 2;
return BinarySearch(target, integers, mid + 1, upper);
}
}
int main() {
int target;
int index;
vector<int> integers = ReadIntegers();
cin >> target;
index = BinarySearch(target, integers, 0, integers.size() - 1);
printf("index: %d, recursions: %d, comparisons: %d\n",
index, recursions, comparisions);
return 0;
}
I AM GETTING THIS ERROR WHEN THE PROGRAM RUNS(SOME ARE CORRECT AND SOME ARE NOT):
![4:Compare output
Output differs. See highlights below.
Input
5:Unit test
Your output
13
10 20 20 20 20 20 25 30 35 40 45 50 60
20
index:
Expected output index: 2, recursions:
Test feedback
recursions:
comparisons: 2
comparisons: 3
Test BinarySearch (99, [11 22 33 44 55 66 77 88 99], 0, 8). Should return 8.
0/2
2/2
inarySearch (99, [11 22 33 44 55 66 77 88 991, 0, 8) correctly returned 8](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fd62cf000-25cd-4cec-89db-6fd9ae34730b%2F541161f8-b649-4d30-9dda-31fea961ee2b%2Fqv98fkq_processed.png&w=3840&q=75)
An array must first be sorted before using the widely used searching algorithm known as binary search. This algorithm's main principle is to divide an array in half repeatedly (divide and conquer) until either the element is found or all the elements have been used up.
It operates by comparing the middle item of the array with our target; if they match, it returns true; if they don't, the left sub-array is searched.
The search is carried out in the appropriate sub-array if the middle term is less than the target.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
