STLなバイナリサーチなり.

BinarySearch.cpp

#include <vector>
#include <iterator>
#include <functional>
#include <cassert>

template <class RandomAccessIterator>
auto binarySearch(RandomAccessIterator first, RandomAccessIterator last,
    typename std::iterator_traits<RandomAccessIterator>::value_type value) -> RandomAccessIterator
{
  std::function<RandomAccessIterator(int, int)> _binarySearch = [&](int imin, int imax) -> RandomAccessIterator {
    if (imin > imax) {
      return last;
    }
    auto imid = (imin + imax) / 2;
    if (first[imid] > value) {
      return _binarySearch(imin, imid - 1);
    } else if (first[imid] < value) {
      return _binarySearch(imid + 1, imax);
    } else {
      return first + imid;
    }
  };
  return _binarySearch(0, static_cast<int>(last - first) - 1);
}

int main() 
{
  std::vector<int> v = {1, 3, 5, 10, 21, 50, 292, 500, 1000, 10000};
  {
    auto i = binarySearch(std::begin(v), std::end(v), 292);
    assert(*i == 292);
  }
  {
    auto i = binarySearch(std::begin(v), std::end(v), 293);
    assert(i == std::end(v));
  }
}