I've got a situation in C++ where I have a costly sub-problem: nearly a minute. Further, this subproblem--bool f(x)--gets longer as x ranges from [1,n].
On the range of [1,n], there is a point 1<j<n, f(j) = true such that f(k), k < j is always false...and f(m), j < m is always true.
I need to find that point.
The way I need to do it is with binary search starting at x=1 (so that it never even touches the time consuming region, where x is close to n).
Right now, I am manually slogging through a binary search implementation where I start at a minimum value for a function (so, f(1), which is false). Then I double the input value until I reach a state where f(x) is happy (true). This part is no big deal. I can do it manually fine.
Next, I want to binary search on the range [x/2,x] for the first value where f(x) = true (noting that f(x/2) must equal false, since f(1) = false...and I need to do it without making any mistakes. And this is where things are getting a little hairy.
So I have a creeping suspicion that C++ has this already implemented, but I am new to C++, and have limited experience with the libraries. I am currently looking at binary search, but I don't see a way to bin search for the actual point at which all values of a function change from false to true.
Rather, it seems to be greedy: it would just grab the first true it finds, rather than the minimum true.
How would I do this in C++?
The inputs of my search function would be as follows:
std::vector<int> range(max);
for (int j = 0; j < max; j++){
range[j] = j;
}
std::some_search_function(range.begin(),range.end(),f(int value))
where f(...) is the boolean function from before...
And it needs to have the properties of what I am describing: start from the first value in the item it is searching, and return the earliest item where f(...) is satisfied...
