Generic Binary Search

[aseemgoyal]

I want to implement a generic binary search algorithm .

Generic : The type can be strings , integers , characters etc .

So , i went through the website and saw implementation of binary_search .

My doubt :
1) How to use compare() function , when we don't know the type . I mean , that comparing strings require str.compare() , but integers can be compared using '>' or '<' .

2) I am always getting the output as in below code . Please explain why .

I have implemented the following (mainly copied from this site):

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<bits/stdc++.h>

using namespace std;

template <class ForwardIterator, class T>
  ForwardIterator lower_ (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  typename iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}
template <class ForwardIterator, class T>
  bool binary_srch (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = lower_(first,last,val);
  return (first!=last && !(val<*first));
}

// Driver program to test above function
int main()
{

vector<string>v;
v.push_back("wefer");
v.push_back("SDAAFS");
v.push_back("ASDFWEaefv");
v.push_back("afea");
v.push_back("jnhfe");

   cout<<binary_srch(v.begin(),v.end(),"jhg");

   return 0;
}

[kbw]

A sort will need to know how to compare and swap items.

There are two good examples of how
to do this. See:
1. qsort
2. std::sort

[Duthomhas]

A binary search requires that the data being searched is sorted. (Your data is not sorted.)

Also, a search is not a predicate: it tells you where something is found in a sequence, not just membership. (Your function returns bool, when it should be returning an iterator.)

I haven't properly perused your algorithm, but I worry it might have an off-by-one access in there. Also, why is "lower_" doing the searching, and not "binary_srch"?

[Smac89]

The best thing to do in this case is to allow the user to supply the function to be used for comparison. So you can have something like:

(C++11)

template <typename T>
using comp = bool (*)(const T&, const T&);

template <typename Iter>
bool binary_srch (Iter , Iter , comp);

(C++03)

#include <functional>
...
template <class Iter, class T>
bool binary_srch (Iter , Iter , bool (*) (const T&, const T&) = std::less<T>());

[giblit]

I mean , that comparing strings require str.compare() , but integers can be compared using '>' or '<' .

Actually you can use relational operators or compare they both do the same thing. http://www.cplusplus.com/reference/string/string/operators/