Binary Search for arrays of different types

[k007]

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);

Thanks for your help
k

[mrnutty]

what does the code return?

[kvprajapati]

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;
}

[k007]

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

[k007]

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