I need to write a template for binary search routine so that it works with arrays of various types (int, char, c style strings). Here is how I have it written,it seems to work when I have a interger array but fails on chars. I need help fixing this.

Binary Search Routine:

template <typename Type>
int rBinarySearch(Type  sortedArray[], int first, int last, Type key, int (*compare)(const void* a, const void* b))
{
Type *keyPtr;
keyPtr=&key;
if (first <= last) {
int mid = (first + last) / 2;  // compute mid point.

Type *midPtr;
midPtr=&sortedArray[mid];
int myResult = compare(keyPtr, midPtr);

if (myResult == 0)
return mid;   // found it.
else if (myResult == -1)
// Call ourself for the lower part of the array
return rBinarySearch(sortedArray, first, mid-1, key, compare);
else
// Call ourself for the upper part of the array
return rBinarySearch(sortedArray, mid+1, last, key, compare);
}

return -1;
}

Compare function

int compare( const void* a, const void* b )
{
int* arg1 = (int*) a;
int* arg2 = (int*) b;
if( *arg1 < *arg2 ) return -1;
else if( *arg1 == *arg2 ) return 0;
else return 1;
}

I also tried changing the compare function to a template but that didnt work either. Here is how I did that

template <typename T>
int compare (const T *a, const T *b)
{
T temp = *a - *b;
if (temp > 0)
return 1;
else if (temp < 0)
return -1;
else
return 0;
}

Here is how I am trying to call the functions:

Array<int> a1(5);
a1.SetMember(0, 3);
a1.SetMember(1, 11);
a1.SetMember(2, 9);
a1.SetMember(3, 13);
a1.SetMember(4, 7);
a1.PrintArray();
a1.SortArray();
a1.PrintArray();
int index=rBinarySearch(a1.getArray(), 1, 4, 9, compare);

The above works.

The following doesnt work

Array<char> a1(5);
a1.SetMember(0, 'k');
a1.SetMember(1, 's');
a1.SetMember(2, 't');
a1.SetMember(3, 'u');
a1.SetMember(4, 'v');
a1.PrintArray();
a1.SortArray();
a1.PrintArray();
int index=rBinarySearch(a1.getArray(), 0, 4, 't', compare);

k

3
Contributors
4
Replies
7
Views
8 Years
Discussion Span
Last Post by k007

what does the code return?

Use typename arguments for compare.

#include <iostream>
using namespace std;

template <typename T,int n>
class Array
{
private:
T *p;
public:
Array() {
p=new T[n];
}
void set(int i,T v) {
*(p+i)=v;
}
void print(){
for(int i=0;i<n;i++){
cout << "\n" << *(p+i);
}
}
~Array(){
delete []p;
}
void sort(){
int i,j;
T y;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(compare(&p[i],&p[j])>0)
{
y=p[i];
p[i]=p[j];
p[j]=y;

}
}
}
}
T *getArray(){
return p;
}
};

template <typename T>
int compare (const T *a, const T *b)
{
T temp = *a - *b;
if (temp > 0)
return 1;
else if (temp < 0)
return -1;
else
return 0;
}

template <typename Type>
int rBinarySearch(Type  sortedArray[], int first, int last, Type key, int (*compare)(const Type* a, const Type* b))
{
Type *keyPtr;
keyPtr=&key;
if (first <= last) {
int mid = (first + last) / 2;  // compute mid point.

Type *midPtr;
midPtr=&sortedArray[mid];
int myResult = compare(keyPtr, midPtr);

if (myResult == 0)
return mid;   // found it.
else if (myResult == -1)
// Call ourself for the lower part of the array
return rBinarySearch(sortedArray, first, mid-1, key, compare);
else
// Call ourself for the upper part of the array
return rBinarySearch(sortedArray, mid+1, last, key, compare);
}

return -1;
}

int main()
{
Array<char,3> a;
a.set(0,'Z');
a.set(1,'R');
a.set(2,'A');
a.sort();
a.print();

cout << "\n" << rBinarySearch(a.getArray(),0,2,'E',compare);

Array<int,3> b;
b.set(0,2);
b.set(1,-3);
b.set(2,4);
b.sort();
cout << "\n" << rBinarySearch(b.getArray(),0,2,2,compare);
return 0;
}

That works like a charm. Thanks for your help. I appreciate it.

Hello,

The modification that you suggested works perfectly when using int or char, but if I use a C-style string, it doesnt, I assumed I would need to do template specialization for the compare function to be able to used with strings and here is what I have done -

template <typename T>
int compare (const T *a, const T *b)
{
T temp = *a - *b;
if (temp > 0)
return 1;
else if (temp < 0)
return -1;
else
return 0;
}

template<>
int compare<char*> (const void *a, const void *b)
{
const char **ia = (const char **)a;
const char **ib = (const char **)b;
return strcmp(*ia, *ib);
}

Here is how I am calling it -

Array<char*,5> a1;
a1.set(0, "tom");
a1.set(1, "nancy");
a1.set(2, "david");
a1.set(3, "john");
a1.set(4, "carla");
a1.print();
a1.sort();
a1.print();
int index=rBinarySearch(a1.getArray(), 0, 4, "nancy", compare);

But it fails to compile -
array.cpp:97: no matching function for call to `rBinarySearch(char**, int, int,
const char[6], <unresolved overloaded function type>)'
array.h: In function `int compare(const T*, const T*) [with T = char*]':
array.h:53: instantiated from `void Array<T, n>::sort() [with T = char*, int n = 5]'
array.cpp:95: instantiated from here
array.h:71: invalid conversion from `int' to `char*'

Thanks
k

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.