#include <cassert>
#include <cmath>
#include <iostream>
#include <utility>

template <typename Domain>
auto midpoint(Domain a, Domain b) { return (a + b) / 2; }

template <typename Function, typename Domain>
std::pair<Domain, Domain> 
root_bisection(Function f, Domain a, Domain b, int steps = 50)
{
  assert(f(a) * f(b) < 0);
  auto ya = f(a);

  while (steps-- > 0)
  {
    auto m = midpoint(a, b);
    auto ym = f(m);
    if (ya * ym < 0) { b = m; }
    else { a = m; ya = ym; }
  }
  return {a, b};
}

int main()
{
  auto f = [](double x) { return std::sin(x); };
  auto x = root_bisection(f, 3.0, 4.0);

  auto a = x.first, b = x.second;
  std::cout << a << " " << b <<  " : " << f(a) << " " << f(b) << '\n';
  return 0;
}