Implementation of binary search

Question

I am trying to implement a version of binary search that is a function template. It is to take two iterators that define the range, and the value it is searching for. If the value is found in the range, the function template is to return an iterator to the value. If not found, it is to return the off-the-end iterator. For simplicity, you must be able to do iterator arithmetic with the iterators provided.

This is what I have so far:

template <typename It, typename T> It binary(It beg, It end, T val) {

        
    It mid = beg + (end - beg) / 2;
    if (*mid == val) 
        return mid;
             
    else if (*mid < val)
        return mid = binary(mid, end, val);
            
    else if (val < *mid) 
        return mid = binary(beg, mid, val);

    return mid;
} 

This function template works fine if the value is found. However, if the value is not found, my program crashes. What happens is that if the value to search for is not found in the range, then the iterator mid gets "stuck" in the sense that it is pointing to either the last element in the container or to the first element in the container. When a recursive call is then made again, mid is recalculated to its exact same position, causing an infinite loop.

I tried to fix it by adding in this piece of code:

template <typename It, typename T> It binary(It beg, It end, T val) {
    //New piece of code
    if (end - beg == 1 and *beg < val)
        return end;
    
    if (end == beg)
        //*** WHAT TO RETURN HERE? ***
    
    //old code
    It mid = beg + (end - beg) / 2;
    if (*mid == val) 
        return mid;
             
    else if (*mid < val)
        return mid = binary(mid, end, val);
            
    else if (val < *mid) 
        return mid = binary(beg, mid, val);

    return mid;
} 

This solves the problem if the value to search for is greater than all of the values in the container, but if the the value to search for is less than all of the values in the container, then what do I return? (see my comment in the code that asks "WHAT DO I RETURN HERE?"). I would like to return an iterator that's one past the last element in the original range, but by the time I have reached the condition where beg == end, I have likely already performed many recursive calls to binary, and thus I have no way to access the original end iterator.

I hope all of that makes sense. I'd appreciate any help. Also, I would like to solve this problem whilst still using recursion.

Answer 1

{
  if (beg==end) return end;

handles the empty range correctly. That is the right answer, fundamentally, to the question you are asking.

The next step is to back up and see how the std library handles it. The std library exposes two functions, lower bound and upper bound, plus one that does both -- equal range.

Lower bound returns the first element not less than the argument, upper bound the first element not less than or equal to the element.

Together, they form a range of elements which, if non-empty, contain the element you want.

The version of your code with

  if (beg==end) return end;

is now lower_bound. You can add in upper_bound and generate equal_range by searching answer to end an element > (aka !<=), where > is just less than with arguments reversed.

Because it makes the code cleaner, I write up a simple range type:

template<class It>
struct range {
  It b, e;

  range(It s, It f):b(s),e(f) {}
  range(It s, std::size_t n):range(s, s+n) {}

  It begin()const{ return b; }
  It end()const{ return e; }

  bool empty()const{ return begin()==end(); }
  std::size_t size()const{ return end()-begin(); }

  range without_front(std::size_t n=1)const{
    n = (std::min)(size(), n);
    return {begin()+n, end()};
  }
  range without_back(std::size_t n=1)const{
    n = (std::min)(size(), n);
    return {begin(), end()-n};
  }

  range only_front(std::size_t n=1)const{
    n = (std::min)(size(), n);
    return {begin(), begin()+n};
  }
  range only_back(std::size_t n=1)const{
    n = (std::min)(size(), n);
    return {end()-n, end()};
  }

  decltype(*std::declval<It const&>()) front()const
  { return *begin(); }
  decltype(*std::declval<It const&>()) back()const
  { return *std::prev(end()); }
};

that bundles a pair of iterators.

template <class It, class T>
range<It> binary(range<It> toSearch, T val) {
 if (toSearch.empty()) return toSearch;
 // note, for a size 1 range, left can be empty
 auto left = toSearch.only_front( toSearch.size()/2 );
 // while right cannot.
 auto right = toSearch.without_front( toSearch.size()/2 );

 // is val only left or right?  If so, recurse
 if (right.front() < val) {
   return binary( right.without_front(1), val );
 } else if (val < right.front()) {
   return binary( left, val );
 }
 // otherwise, right.front() == val at this point
 // find entire range recursively:
 auto lhs = binary(left, val);
 auto rhs = binary(right, val);
 return {lhs.begin(), rhs.end()};
} 

so now we have a fun function that finds the range of elements equal to val.

We then implement your problem:

template <typename It, typename T>
It binary(It beg, It end, T val) {
  auto r = binary( range<It>{beg,end}, val );
  if (r.empty()) return end;
  return r.begin();
}

and done.

You'll note this code only uses < to compare values, it never checks for ==. This matches how the std library does it.

In general there are 2 special cases in a binary search; the empty one, and the 1 element one. The above handles the empty one explicity; the 1 element one is handled implicitly by .without_front(1), which is also an optimization on the general search (we already eliminated the front element of the right from consideration).

Another fun thing is this code:

if (right.front() < val) {
  return binary( right.without_front(1), val );
} else if (val < right.front()) {
  return binary( left, val );
}

we really want a 3-way comparison here. In C++17, we get <=> which does exactly that. This isn't a coincidence.