Search code examples
rbinary-search

Binary Search the hightes value for which a function is false in R

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)
Solution

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