Binary Search on a std::string array

Question

Below is the code and

std::string str[5] = {"Tejas","Mejas","Rajas","Pojas","Ljas"};
std::sort(str,str+5);
size_t test =  bin_search("Ljas",str,5);

Here is the generic function for binary search

 template<class T>
    size_t bin_search(T x,  T* array, int  n)
     {
     size_t begin = 0, end = n;
            // Invariant: This function will eventually return a value in      the range [begin, end]
             while (begin != end) {
                       size_t mid = (begin + end) / 2;
                       if (array[mid] < x) {
                              begin = mid + 1;
                       } else {
                                 end = mid;
                       }
      }
     return begin;   // Or return end, because begin == end
}

And the Error is

 main.cpp|12|error: no matching function for call to 'bin_search(const char [5], std::string [5], int)'|

There is a problem with only the std::string array, but the int array works really fine. Does it work with string arrays or is there anything missing in the logic?

Answer 1

As the error message tried to tell you, "Ljas" is not std::string, it's const char[5]. Then the template argument deduction failed since the type T could not be deduced (as const char* or std::string).

You could explicitly cast it to std::string to make template argument deduction work well:

size_t test =  bin_search(std::string("Ljas"),str,5);

or explicitly specify the template argument to avoid template argument deduction:

size_t test =  bin_search<std::string>("Ljas",str,5);

Answer 2

template<class T>
size_t bin_search(T x,  T* array, int  n)

Expects that you recieve a T and a pointer to T. When the compiler deducts the types in

size_t test =  bin_search("Ljas",str,5);

x is deduced as a const char[5] as all string literals have the type const char[N]. array is deduced std::strign[5]. Since a cont char[] and a std::string[] are not the same type the no function will be generated. You need to make "Ljas" a string like

size_t test =  bin_search(std::string("Ljas"),str,5);

---

Also note that the collection passed to a binary search needs to be sorted. If the data is not sorted then you cannot reason what half the element should be in.