Answer in C++ and only edit the searcher h Implement the Searcher class's BinarySearch() template function in
Question:
Answer in C++ and only edit the searcher h
Implement the Searcher class's BinarySearch() template function in the Searcher.h file. Access Searcher.h by clicking on the orange arrow next to main.cpp at the top of the coding window. The function performs a binary search on the sorted array (first parameter) for the key (third parameter). BinarySearch() returns the key's index if found, -1 if not found.
Compare an array element to the key using the Compare() member function of the comparer object passed as BinarySearch()'s last parameter. comparer.Compare(a, b) returns an integer:
- greater than 0 if a > b
- less than 0 if a < b
- equal to 0 if a == b
A few test cases exist in main() to test BinarySearch() with both string searches and integer searches. Clicking "Run program" will display test case results, each starting with "PASS" or "FAIL". Ensure that all tests are passing before submitting code.
Each test in main() only checks that BinarySearch() returns the correct result, but does not check the number of comparisons performed. The unit tests in the submit mode check both BinarySearch()'s return value and the number of comparisons performed.
Searcher h
#ifndef SEARCHER_H
#define SEARCHER_H
#include "Comparer.h"
template
class Searcher {
public:
// Returns the index of the key in the sorted array, or -1 if the key is not
// found
static int BinarySearch(T* array, int arraySize, const T& key,
Comparer& comparer) {
// Your code here (remove placeholder line below)
return -1;
}
};
#ifndef COMPARER_H
#define COMPARER_H
// Comparer is an abstract base that can compare two items with the Compare()
// function. The Compare() function compares items a and b and returns an
// integer:
// - greater than 0 if a > b,
// - less than 0 if a < b, or
// - equal to 0 if a == b
template
class Comparer {
public:
virtual int Compare(const T& a, const T& b) = 0;
};
#endif
main cpp
#include
#include
#include "Comparer.h"
#include "StringComparer.h"
#include "IntComparer.h"
#include "Searcher.h"
using namespace std;
// Implementation of PrintSearches is below main()
template
void PrintSearches(T* sortedArray, int sortedArraySize, T* searchKeys,
int searchKeysSize, Comparer& comparer, int* expectedResults,
bool keyInQuotes);
int main(int argc, char *argv[]) {
// Perform sample searches with strings
string sortedFruits[] = { "Apple", "Apricot", "Banana", "Blueberry",
"Cherry", "Grape", "Grapefruit", "Guava", "Lemon", "Lime", "Orange",
"Peach", "Pear", "Pineapple", "Raspberry", "Strawberry"
};
int sortedFruitsSize = sizeof(sortedFruits) / sizeof(sortedFruits[0]);
string fruitSearches[] = { "Nectarine", "Mango", "Guava", "Strawberry",
"Kiwi", "Apple", "Raspberry", "Carrot", "Lemon", "Bread"
};
int fruitSearchesSize = sizeof(fruitSearches) / sizeof(fruitSearches[0]);
int expectedFruitSearchResults[] = { -1, -1, 7, 15, -1, 0, 14, -1, 8, -1 };
StringComparer stringComparer;
PrintSearches(sortedFruits, sortedFruitsSize, fruitSearches,
fruitSearchesSize, stringComparer, expectedFruitSearchResults, true);
// Perform sample searches with integers
int integers[] = {
11, 21, 27, 34, 42, 58, 66, 71, 72, 85, 88, 91, 98
};
int integerSearches[] = {
42, 23, 11, 19, 87, 98, 54, 66, 92, 1, 14, 21, 66, 87, 83
};
int expectedIntegerSearchResults[] = {
4, -1, 0, -1, -1, 12, -1, 6, -1, -1, -1, 1, 6, -1, -1
};
IntComparer intComparer;
PrintSearches(integers, sizeof(integers) / sizeof(integers[0]),
integerSearches, sizeof(integerSearches) / sizeof(integerSearches[0]),
intComparer, expectedIntegerSearchResults, false);
return 0;
}
template
void PrintSearches(T* sortedArray, int sortedArraySize, T* searchKeys,
int searchKeysSize, Comparer& comparer, int* expectedResults,
bool keyInQuotes) {
// If keyInQuotes is true, " characters surround the key in output
// statements. Otherwise empty strings surround the key.
string extra = keyInQuotes ? """ : "";
// Iterate through array of search keys and search for each
for (int i = 0; i < searchKeysSize; i++) {
// Get the key to search for
auto searchKey = searchKeys[i];
// Peform the search
int index = Searcher::BinarySearch(sortedArray, sortedArraySize,
searchKey, comparer);
// Compare actual result against expceted
int expected = expectedResults[i];
if (index == expected) {
cout << "PASS: Search for key " << extra << searchKey << extra;
cout << " returned " << expected << "." << endl;
}
else {
cout << "FAIL: Search for key " << extra << searchKey << extra;
cout << " should have returned " << expected << ", but returned ";
cout << index << "." << endl;
}
}
}
#ifndef STRINGCOMPARER_H
#define STRINGCOMPARER_H
#include
#include "Comparer.h"
// StringComparer inherits from Comparer and so provides the
// ability to compare two std::string objects.
class StringComparer : public Comparer {
public:
int Compare(const std::string& a, const std::string& b) override {
return a.compare(b);
}
};
#endif
#ifndef INTCOMPARER_H
#define INTCOMPARER_H
#include "Comparer.h"
// IntComparer inherits from Comparer and so provides the
// ability to compare two integers.
class IntComparer : public Comparer {
public:
int Compare(const int& a, const int& b) override {
if (a < b) {
return -1;
}
else if (a > b) {
return 1;
}
return 0;
}
};
#endif
Probability and Statistics for Engineers and Scientists
ISBN: 978-0495107576
3rd edition
Authors: Anthony Hayter