Binary search equivalent for `find_if`

Question

Suppose a container (in this case a plain array) storing elements like

struct Foo
    {
    char id[8];
    // other members
    };

Now I want to find a Foo whose id begins with a particular string S. Since the array is sorted by id, I want to use binary search, so I look for a function which perform binary search with the same interface as find_if. Is there such a function in STL, can it be constructed by using other elements in algorithm, or do I need to implement it my self.

Answer 1

You are looking for std::lower_bound, std::upper_bound and std::equal_range, which take an input range, a search value and an optional comparator and require the range to be sorted according to comparator.

For your specific example, I'd use std::lexicographical_compare for the comparator:

#include <algorithm>
#include <iterator>

struct IdCmp
{
  bool operator()(const Foo & lhs, const Foo & rhs) const
  {
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id),
                                        std::begin(rhs.id), std::end(rhs.id));
  }
};

int main()
{
  Foo a[100];           // populate
  Foo b = make_needle();

  auto p = std::equal_range(std::begin(a), std::end(a), b, IdCmp());

  /* The elements with key equal to that of b are in [p.first, p.second). */
}

If you want to be able to search for strings directly, your comparator needs to be callable heterogeneously with one Foo argument and one string argument. For example:

struct IdCmp
{
  bool operator()(const Foo & lhs, const Foo & rhs) const
  {
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id),
                                        std::begin(rhs.id), std::end(rhs.id));
  }

  bool operator()(const Foo & lhs, const char * id) const
  {
    return std::lexicographical_compare(std::begin(lhs.id), std::end(lhs.id),
                                        id, id + 8);
  }

  bool operator()(const char * id, const Foo & rhs) const
  {
    return std::lexicographical_compare(id, id + 8,
                                        std::begin(rhs.id), std::end(rhs.id));
  }
};

Now you can search:

std::lower_bound(std::begin(a), std::end(a), "ABCD1234", IdCmp())