Description Usage Arguments Details Value Examples
View source: R/binary_search.R
Find the position of a given value in a sorted array
1 2 3 | binsearch(val, arr, L = 1L, H = length(arr))
binclosest(val, arr, L = 1L, H = length(arr))
|
val |
the value to search for |
arr |
a sorted array to make the search in |
L |
a lower bound |
H |
an upper bound |
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.
A single integer representing an index on the input array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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)
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.