Binary search equivalent for `find_if`

c++, stl, stl-algorithm

Solution

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

Problem

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.

Original source