Listing 4: A generic median algorithm for sorted ranges

template<typename _It>
double median(_It beg, _It end)
{
  typedef std::iterator_traits<_It>::difference_type difftype;

  if( beg == end )
    return 0.0;

  difftype diffLen = std::distance(beg, end);
  int nLen = static_cast<int>(diffLen);
  int nHalfLen = nLen / 2;
  difftype diffHalfLen = static_cast<difftype>(nHalfLen);
  difftype diffOne = static_cast<difftype>(1);
  
  _It mid = beg;
  if( 1 == nLen % 2 )
  {
    std::advance(mid, diffHalfLen);
    return *mid;
  }
  else
  {
    std::advance(mid, diffHalfLen - diffOne);
    _It next = mid;
    ++next;
    return 
      (static_cast<double>(*mid) + static_cast<double>(*next)) / 2.0;
  }
}
— End of Listing —