You will be converting the binary search function into a template version (see l
ID: 645892 • Letter: Y
Question
You will be converting the binary search function into a template version (see lecture 7 for binary search reference). And this template version of binary search function should be able to work with different data types. In this lab, we are going to use both std::list and std::vector.
Since now the template binary search function is generic for both list and vector, when you traverse the elements inside a list or a vector using iterators, you should probably use std::advance and std::distance instead of the +/- and +=/-= operators, because the latter only work with random access iterators (although std::advance(iterator, 1) and ++iterator do the same thing).
Input: Only looking for 7 in both vector and list
vector v = {1, 2, 5, 7, 9, 13, 15, 18}
list l = {1, 2, 3, 4, 5, 6, 7, 8}:
*Should look something like this
iterator I = binarySearch(v.begin(), v.end(), 7);
iterator J = binarySearch(l.begin(), l.end(), 7);
Output:
7 is in the 4th position in the vector.
7 is in the 7th position in the list.
Explanation / Answer
#include
#include
#define N 100;
using namespace std;
template
int binarySearch(T *a, T item, int n)
{
int beg=0,end=n-1;
int mid=beg+end/2;
while((a[mid]!=item) && (n>0))
{
if(item>a[mid])
beg=mid;
else
end=mid;
mid=(beg+end)/2;
n--;
}
if(a[mid]==item)
return (mid+1);
else
return -1;
}
void main()
{
int list[N];
std::vector<int> vec (N,0);
int item,num;
num=list.size();
cout<<" Elements of Integer List ";
for(int i=0;i
{
cout<<" "<
}
num=vec.size();
cout<<" Elements of Integer List ";
for(int i=0;i
{
cout<<" "<
}
cout<<" Enter an item to be search: ";
cin>>item;
cout<<" Binary Search method ";
iteratorI= binarySearch(list,item,num);
iteratorJ=binarySearch(vec,item,num);
if(iteratorI==-1)
{cout<
else
{cout<
if(iteratorJ==-1)
{cout<
else
cout<
system("pause");
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.