Question

Question 2 (Function Template)

Write a template version of the iterative binary search algorithm that searches an array of arbitrary type for a given key.

Declare and implement a class called Student that keeps the student id, name, and grade. Include a default constructor, the overloaded insertion (<<) operator and also the overloaded extraction operator (>>).

Declare and implement another class called Book that keeps the book’s title, author, and price. Just like the Student class, Include in class Book a default constructor, the overloaded insertion (<<) operator and also the overloaded extraction operator (>>).

Write a main() function that test your function by passing parameters of type int, float, char, Student, and Book. Identify and implement additional suitable operators needed to be overloaded in the Student and Book class that you define above so that it can work well with the template binary search function that you have written. A Student object should be searched using the student id and the Book object should be searched using its title.

Answer 1

Code:

Code as text:

#include <iostream>

using namespace std;

// Template of iterative binary search

template<class T> int binarySearch(T arr[], int size, T target) {

int low = 0;

int high = size - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (target < arr[mid])

high = mid - 1;

else if (target > arr[mid])

low = mid + 1;

else

return mid;

}

return -1;

}

// a class for student

class Student {

private:

int id;

string name;

char grade;

public:

Student(int _id, string _name, char _grade) {

id = _id;

name = _name;

grade = _grade;

}

friend ostream &operator<<(ostream &out, Student &S) {

out << "Student id: " << S.id << "\nName: " << S.name << "\nGrade: " << S.grade;

return out;

}

friend istream &operator>>(istream &input, Student &S) {

input >> S.id >> S.name >> S.grade;

return input;

}

bool operator<(Student &S) {

if (id < S.id)

return true;

else

return false;

}

bool operator>(Student &S) {

if (id > S.id)

return true;

else

return false;

}

bool operator<=(Student &S) {

if (id <= S.id)

return true;

else

return false;

}

};

// a class for book

class Book {

private:

string title;

string author;

float price;

public:

Book(string _title, string _author, float _price) {

title = _title;

author = _author;

price = _price;

}

friend ostream &operator<<(ostream &out, Book &B) {

out << "Book Title: " << B.title << "\nAuthor: " << B.author << "\nPrice: " << B.price;

return out;

}

friend istream &operator>>(istream &input, Book &B) {

input >> B.title >> B.author >> B.price;

return input;

}

bool operator<(Book &B) {

if (title < B.title)

return true;

else

return false;

}

bool operator>(Book &B) {

if (title > B.title)

return true;

else

return false;

}

bool operator<=(Book &B) {

if (title <= B.title)

return true;

else

return false;

}

};

int main() {

int pos; // to store position of search element

int size; // to store size of array

// test int array

cout << "Testing on type: int" << endl;

int intArr[] = {1, 3, 4, 6, 7, 9, 13, 15};

size = sizeof(intArr) / sizeof(*intArr);

int targetInt = 7;

pos = binarySearch(intArr, size, targetInt);

cout << "Target found at position: " << pos << endl;

cout << endl;

// test float array

cout << "Testing on type: float" << endl;

float floatArr[] = {23.0, 56.7, 69.9, 142.8, 299.3};

size = sizeof(floatArr) / sizeof(*floatArr);

float targetfloat = 69.9;

pos = binarySearch(floatArr, size, targetfloat);

cout << "Target found at position: " << pos << endl;

cout << endl;

// test char array

cout << "Testing on type: char" << endl;

char charArr[] = {'A', 'D', 'E', 'H', 'L', 'P', 'S', 'W', 'Z'};

size = sizeof(charArr) / sizeof(*charArr);

char targetchar = 'L';

pos = binarySearch(charArr, size, targetchar);

cout << "Target found at position: " << pos << endl;

cout << endl;

// test student array

cout << "Testing on type: Student" << endl;

Student studArr[] = {{1, "AJ", 'A'}, {2, "DK", 'F'}, {3, "AS", 'C'}};

size = sizeof(studArr) / sizeof(*studArr);

Student targetStud(2, "DK", 'F');

pos = binarySearch(studArr, size, targetStud);

cout << "Target found at position: " << pos << endl;

cout << endl;

// test book array

cout << "Testing on type: Book" << endl;

Book bookArr[] = {{"XYZ", "ABC", 32.0}, {"HSJ", "NMJ", 50.2}};

size = sizeof(bookArr) / sizeof(*bookArr);

Book targetBook("XYZ", "ABC", 32.0);

pos = binarySearch(bookArr, size, targetBook);

cout << "Target found at position: " << pos << endl;

return 0;

}

Sample run:

P.s. Ask any doubts in comments and don't forget to rate the answer.