binary search over function arguments with/without boost

Question

Given the:

typedef .../*some type*/ SomeValue;

SomeValue someFunction(int arg){
     return /*some calculation involving arg that produces SomeValue*/
}

int firstCandidate = 0, lastCandidate = 101;
SomeValue desiredValue = SomeValue();

I want to find int argument which produces desiredValue(when passed to someFunction) using binary search (std::lower_bound). firstCandidate, lastCandidate are parameters to be given to someFunction. For search candidates std::lower_bound should call someFunction(currentArgument) and compare result with desiredValue. for SomeValue someFunction(x) < someFunction(x + 1) is true.

I.e. it should produce same result as this:

int findArgLowerbound(int first, int last, SomeValue refVal){
     for (int i = first; i < last; i++){
          if (someFunction(i) >= refVal)
               return i;
     }
     return last;
}

only using standard functions + binary search algorithm.

How can I do that EASILY (without writing my own binary search function) with and without boost? int is not iterator, and I haven't figured out how to make boost::make_transform_iterator in this case.

restrictions:

1. c++03 standard.
2. boost is okay, but I'd really prefer solution without it.

--edit--

I want to know how can I use built-in or already-available functions (std::lower_bound and similar) do what I want. I could write specialized binary search function, but I don't think that'll be the "right" way to do it.

Answer 1

figured it out (enjoy the macro+template voodoo).

#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/irange.hpp>
#include <boost/typeof/std/utility.hpp>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <sstream>

std::string convertArgs(int arg1, int arg2){
    std::stringstream out;
    out << std::setfill('0') << std::setw(8) << arg1*arg2;
    return out.str();
}

void boostTest(){
    int first = 0, last = 42;
    int arg = 2;
    std::string desiredValue = "00000007";
    BOOST_AUTO(range, boost::irange(first, last));
    BOOST_AUTO(start, boost::make_transform_iterator(range.begin(), std::bind1st(std::ptr_fun(convertArgs), arg)));
    BOOST_AUTO(end, boost::make_transform_iterator(range.end(), std::bind1st(std::ptr_fun(convertArgs), arg)));
    BOOST_AUTO(found, std::lower_bound(start, end, desiredValue));
    if (found != end){
        std::cout << "str:" << *found << "\nval: " << *(found.base());
    }
}

int main(int argc, char** argv){
    boostTest();
    return 0;
}

Most likely, can't be done easily without boost unless you generate arrays with all possible values, make wrapper iterators yourself or something like that.

Answer 2

This is how I would approach it:

Pretend you have a vector<SomeValue> that is sorted. This vector is accessible using someFunction(index).

Now, look at this. That is pseudocode for the binary search. Continuing with the thought process above, replace A[imid] with someFunction(imid) and make key a SomeValue. Make sure SomeValue has a valid operator < (or a comparator function that you use in place of it).

This will of course only work if someFunction(x) < someFunction(x + 1) for all x. You have stated this to be true, so it should be good.

I would suggest using the iterative approach because both have the same asymptotic runtime, and the iterative version makes it easier to report a key that was not found, and tends to use less memory.

EDIT I am unaware of a simple way to do it using the std stuff. As you mentioned above, int wouldn't work as an iterator, and all of the functions that you would probably want to use take iterators. Technically though, the iterators in these functions are templated types, so you write your own IntIter class or something like that. Using std::lower_bound would need the operator *(), operator ++(), and operator +(int). operator *() would probably return someFunction(n), where n is the int value associated with the IntIter. However, I don't know if this would actually work, and it would probably take more time and coding. You should look at std::lower_bound and std::advance (called in lower_bound) if you want to take this approach.