binsearch: Binary search

In AkselA/R-ymse: Ymse (Various)

Description

Find the position of a given value in a sorted array

Usage

binsearch(val, arr, L = 1L, H = length(arr))

binclosest(val, arr, L = 1L, H = length(arr))

Arguments

val	the value to search for
arr	a sorted array to make the search in
L	a lower bound
H	an upper bound

Details

While both val and arr can be either integer or double, the algorithm is limited by integer storage in how long the array can be. L and H can be used to limit the range of indices to be search within.
binsearch will return either the index of the exact match, or the index just below if no exact match is found. This means that if val is less than the lowest value in arr (and L=1), a 0 will be returned, which can lead to issues as such an index does not exist in R. An array indexed by 0 will return a zero length object. binclosest will return the index of the closest match, and therefore a 1 in the situation where binsearch returns a 0. If there is a tie the lower index will be returned.
In either case, if there are duplicate matches, the lower index will be returned.

Value

A single integer representing an index on the input array.

Examples

binsearch(15, (1:9)*3.333)
binsearch(2, (1:9)*3.333)
binclosest(2, (1:9)*3.333)

binsearch(18, seq_len(2e9))
## Not run: 
binsearch(18, seq_len(3e9))
## End(Not run)
binsearch(18, seq_len(3e9), H=2e9)
binsearch(2000, seq_len(3e7)*100 + 0.1)

set.seed(1)
x <- sort(sample(1:300, 30))
r <- sort(sample(1:300, 30))

plot(sapply(r, binsearch, x), type="l")
lines(sapply(r, binclosest, x), col="red")

x <- c(1, 2, 3, 5, 8, 9)
binclosest(6, x)
binclosest(7, x)
binclosest(5, x)

AkselA/R-ymse documentation built on March 21, 2020, 9:52 a.m.