CODEWITHSUNDEEP
c++algorithm
Chris
Chris

Reputation: 31206

How to implement binary search on function in C++?

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...

Upvotes: 0

Views: 153

Answers (1)

kraskevich
kraskevich

Reputation: 18556

You can implement a custom iterator that "points" to true or false depending on the index it represents and use std::lower_bound function to find the first true value.

Upvotes: 3

Related Questions