Why is binsearch limited to ranges larger than 1?

[brooksambrose]

binsearch appears to have an arbitrary precision of 1, such that ranges that occur, for instance, between 0 and 1 cannot be searched. For example, the function cannot find x = .1 in this simple example. I admit this would require a user defined precision, but the presumed precision hard coded into the routine is 1, which isn't very precise for many applications. Thanks, I may not fully understand the background here and am happy to have it explained to me.

Note also that the default values for upper and lower covert the range c(0.01,0.99) to c(1,0), which reverses their order and is another example of the integer precision presumption.

It took me a while to understand why binsearch wasn't working for my function, until I noticed the "between integers" stopping rule, so I modified my scales with an adjustment factor as below:

gtools::binsearch(function(x) x - 0.1, range = c(0.01, 0.99))
#> $call
#> gtools::binsearch(fun = function(x) x - 0.1, range = c(0.01, 
#>     0.99))
#> 
#> $numiter
#> [1] 1
#> 
#> $flag
#> [1] "Between Elements"
#> 
#> $where
#> [1] 1 0
#> 
#> $value
#> [1]  0.9 -0.1

^{Created on 2024-06-29 with reprex v2.1.0}

[bbolker]

Well, the documentation does say:

Search within a specified range to locate an integer parameter

(emphasis added).

The last paragraph of "Details" also suggests that a search over the integers is the intended use case here.

What is your use case? Is there a particular reason that binary search would be better than base R's uniroot() function?

[brooksambrose]

Fair enough. It took me a while to understand why binsearch wasn't working for my function, until I noticed the "between integers" stopping rule, so I modified my scales with an adjustment factor as below. Perhaps a note in the the documentation alerting the user to how to adjust for this use case would be helpful.

l=0.01
h=0.99
adj<-1/l
x<-gtools::binsearch(function(x) x/adj - 0.1, range = c(l, h),lower=l*adj,upper=h*adj)
x
#> $call
#> gtools::binsearch(fun = function(x) x/adj - 0.1, range = c(l, 
#>     h), lower = l * adj, upper = h * adj)
#> 
#> $numiter
#> [1] 6
#> 
#> $flag
#> [1] "Found"
#> 
#> $where
#> [1] 10
#> 
#> $value
#> [1] 0
x$where/adj
#> [1] 0.1

^{Created on 2024-06-29 with reprex v2.1.0}

[brooksambrose]

I'm looking at binary search because the function is very expensive and I want to run the fewest number of estimates. I'm not sure how uniroot works but I'll take a look, thanks.

[bbolker]

Brent's method (which underlies uniroot()) is more efficient than bisection, but R's implementation only allows you to set a tolerance on the objective function, not on the magnitude of the error in x (nor to set a maximum number of iterations). Nevertheless, if you can pick your tolerance appropriately you should be able to do better (on average fewer function evaluations to reach a specified tolerance) with uniroot() than with binsearch ...

*