IncreasingIntExprFunctionElement::SetRange inefficient on large ranges

[GoogleCodeExporter]

As I understand it, given a monotonicly increasing function f and range 
(min,max), IncreasingIntExprFunctionElement::SetRange tries to find (nmin,nmax) 
such that (f(nmax+1) > max >= f(nmax)) and similarly for nmin.

The function simply iterates over the range until it finds nmin and nmax -

     int64 nmax = expression_max;
     while (nmax >= expression_min && values_->Run(nmax) > ma) {
       nmax--;
     }

This doesn't work very well for large ranges. For my purposes, I've found that 
a binary search is much better -

     typedef boost::counting_iterator<int64> bci;
     bci bmin = bci(expression_min);
     bci bmax = bci(expression_max + 1);
     bci b = std::upper_bound(bmin, bmax, ma, [this] (int64 ma, int64 nmax) { return ma < values_->Run(nmax); });
     nmax = std::max(expression_min, *(b-1));

Original issue reported on code.google.com by sude...@gmail.com on 16 Feb 2015 at 9:59