C++ I am trying to build a template binary search function. I have the follwoing

Question

C++

I am trying to build a template binary search function. I have the follwoing, but it keeps getting stuck in a continous loop. Can someone help me fix this code so that it runs.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
bool binarySearch(vector<T> &a, T item) {
int first = 0;
int last = a.size() - 1;

cout << last;
bool found = false;
int midpoint = first + last/2;

while(first <= last && found != true){
if(a[midpoint] == item) {
found = true;
} else {
if(item > midpoint)
first = midpoint + 1;
else
last = midpoint - 1;
}
}

return found;

}

int main()
{
vector<int> nums;

nums.push_back(2);
nums.push_back(4);
nums.push_back(6);
nums.push_back(8);
nums.push_back(10);
nums.push_back(12);
nums.push_back(14);

binarySearch(nums, 2);
binarySearch(nums, 3);

return -1;
}

Explanation / Answer

/*
I am trying to build a template binary search function. I have the follwoing, but it keeps getting stuck in a continous loop. Can someone help me fix this code so that it runs.
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <typename T>
bool binarySearch(vector<T> &a, T item) {
int first = 0;
int last = a.size() - 1;
bool found = false;
int midpoint = first + last/2;
  
// In each iteration, you gotta update midpoint as well along with variables first or last
while (first <= last && found != true) {
if(a[midpoint] == item) {
found = true;
} else {
if(item > midpoint)
{
first = midpoint + 1;
  
// MID point should be calculated again
midpoint = first + last/2;
}
else
{
last = midpoint - 1;
  
// mid point should be first
midpoint = first;
}
}
  
  
}
return found;
}
int main()
{
vector<int> nums;
nums.push_back(2);
nums.push_back(4);
nums.push_back(6);
nums.push_back(8);
nums.push_back(10);
nums.push_back(12);
nums.push_back(14);

cout << binarySearch(nums, 2) << endl;
cout << binarySearch(nums, 3);

return 0;
}

/*OUTPUT
1
0
*/

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.