15.14 LAB: Binary search   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 ATTENTION WHERE IT SAYS CODE HERE, IS WHERE I MUST ADD CODE. EVERYTHING ELSE CANNOT BE ALTERED #include #include #include using namespace std; // Read integers from input and store them in a vector. // Return the vector. vector ReadIntegers() {    int size;    cin >> size;    vector 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 integers, int lower, int upper) {    /* code here. */ } int main() {    int target;    int index;    vector integers = ReadIntegers();    cin >> target;    index = BinarySearch(target, integers, 0, integers.size() - 1);    printf("index: %d, recursions: %d, comparisons: %d\n",           index, recursions, comparisons);    return 0; }

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
icon
Concept explainers
Question

15.14 LAB: Binary search

 

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:

  1. Parameters:
    • a target integer
    • a vector of integers
    • lower and upper bounds within which the recursive call will search
  2. 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.

  1. If target == integers.at(index) return index
  2. If lower == upper, return -1 to indicate not found
  3. 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():

  1. Count the number of calls to BinarySearch().
  2. 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:

  1. the number of integers in the vector
  2. the integers in the vector
  3. 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

ATTENTION

WHERE IT SAYS CODE HERE, IS WHERE I MUST ADD CODE. EVERYTHING ELSE CANNOT BE ALTERED

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 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) {
   /* code here. */
}

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, comparisons);

   return 0;
}

Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 2 images

Blurred answer
Knowledge Booster
Types of Linked List
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education