I have an expensiv function that can be called with an positive integer. Starting at zero this function returns false, at a certain value (call this value y) the function will return true and will return also true for all inputvalues higher than y.

What i tried: I defined a function (in reality this function takes a very long time to execute)

magicFun <- function(x) x > 10

detect (Package purrr) does work, but is too slow for my use case (remember in my case magicFun takes a lot of time)

> detect(0:100,magicFun)
[1] 11

binsearch (Package gtools) does not work, as it will return the first value that returns false (but I want the highest value)

binsearch(magicFun, range = c(0,100), showiter = T)

CodePudding user response：

Use

binsearch(magicFun, range = c(0,100), showiter = T, target = 0.5)

This tells the search algorithm to look for 0.5, which is in the middle of TRUE and FALSE. It will return the largest FALSE and the smallest TRUE.

If this is still too slow, then you'll have to optimize the expensive function.

CodePudding user response：

You will need to write this yourself, because you have unusual needs, i.e. you do not want to pass a vector to magicFun, you only want to pass scalars, you want to pass as few as possible of those, and you don't have a typical stopping rule: you need to stop at n where magicFun(n) is TRUE but magicFun(n-1) is FALSE.

Do you have any idea about how big the answer will be in advance? If for example you think it will be around 100, you could start a binary search at 0 and 120. You will need to be prepared for your initial guess to be wrong, i.e. maybe 120 gives FALSE.

I'll let you write the function yourself.