binsearch: Binary Search

In gtools: Various R Programming Tools

Binary Search

Description

Search within a specified range to locate an integer parameter which results in the the specified monotonic function obtaining a given value.

Usage

binsearch(
  fun,
  range,
  ...,
  target = 0,
  lower = ceiling(min(range)),
  upper = floor(max(range)),
  maxiter = 100,
  showiter = FALSE
)

Arguments

fun	Monotonic function over which the search will be performed.
range	2-element vector giving the range for the search.
...	Additional parameters to the function fun.
target	Target value for fun. Defaults to 0.
lower	Lower limit of search range. Defaults to min(range).
upper	Upper limit of search range. Defaults to max(range).
maxiter	Maximum number of search iterations. Defaults to 100.
showiter	Boolean flag indicating whether the algorithm state should be printed at each iteration. Defaults to FALSE.

Details

This function implements an extension to the standard binary search algorithm for searching a sorted list. The algorithm has been extended to cope with cases where an exact match is not possible, to detect whether that the function may be monotonic increasing or decreasing and act appropriately, and to detect when the target value is outside the specified range.

The algorithm initializes two variable lo and high to the extremes values of range. It then generates a new value center halfway between lo and hi. If the value of fun at center exceeds target, it becomes the new value for lo, otherwise it becomes the new value for hi. This process is iterated until lo and hi are adjacent. If the function at one or the other equals the target, this value is returned, otherwise lo, hi, and the function value at both are returned.

Note that when the specified target value falls between integers, the two closest values are returned. If the specified target falls outside of the specified range, the closest endpoint of the range will be returned, and an warning message will be generated. If the maximum number if iterations was reached, the endpoints of the current subset of the range under consideration will be returned.

Value

A list containing:

call	How the function was called.
numiter	The number of iterations performed
flag	One of the strings, "Found", "Between Elements", "Maximum number of iterations reached", "Reached lower boundary", or "Reached upper boundary."
where	One or two values indicating where the search terminated.
value	Value of the function fun at the values of where.

Note

This function often returns two values for where and value. Be sure to check the flag parameter to see what these values mean.

Author(s)

Gregory R. Warnes [e-mail]

See Also

optim, optimize, uniroot

Examples

### Toy examples

# search for x=10
binsearch(function(x) x - 10, range = c(0, 20))

# search for x=10.1
binsearch(function(x) x - 10.1, range = c(0, 20))

### Classical toy example

# binary search for the index of 'M' among the sorted letters
fun <- function(X) {
  ifelse(LETTERS[X] > "M", 1,
    ifelse(LETTERS[X] < "M", -1, 0)
  )
}

binsearch(fun, range = 1:26)
# returns $where=13
LETTERS[13]

### Substantive example, from genetics
## Not run: 
library(genetics)
# Determine the necessary sample size to detect all alleles with
# frequency 0.07 or greater with probability 0.95.
power.fun <- function(N) 1 - gregorius(N = N, freq = 0.07)$missprob

binsearch(power.fun, range = c(0, 100), target = 0.95)

# equivalent to
gregorius(freq = 0.07, missprob = 0.05)

## End(Not run)

gtools documentation built on Nov. 20, 2023, 5:07 p.m.