bsearch: Binary Search with Approximate Matching

In matter: A framework for rapid prototyping with file-based data structures

Description

Given a set of keys and a sorted (non-decreasing) vector of values, use a binary search to find the indexes in values that match the values of key. This implementation allows for returning the index of the nearest match if there are no exact matches. It also allows specifying a tolerance for comparison of doubles.

Usage

bsearch(key, values, tol = 0, tol.ref = "none",
		nomatch = NA_integer_, nearest = FALSE)

Arguments

key	A vector of keys to match.
values	A sorted (non-decreasing) vector of values to be matched.
tol	The tolerance for matching doubles. Must be >= 0.
tol.ref	One of 'none', 'key', or 'values'. If 'none', then comparison of doubles is done by taking the absolute difference. If either 'key' or 'values', then relative differences are used, and this specifies which to use as the reference (target) value.
nomatch	The value to be returned in the case when no match is found, coerced to an integer. (Ignored if nearest = TRUE.)
nearest	Should the index of the closest match be returned if no exact matches are found?

Details

The algorithm is implemented in C and currently only works for 'integer', 'numeric', and 'character' vectors. If there are multiple matches, then the first match that is found will be returned, with no guarantees. If a nonzero tolerance is provided, the closest match will be returned.

The "nearest" match for strings when there are no exact matches is decided by the match with the most initial matching characters. Tolerance is ignored for strings and integers. Behavior is undefined and results may be unexpected if values includes NAs.

Value

A vector of the same length as key, giving the indexes of the matches in values.

Author(s)

Kylie A. Bemis

See Also

match, pmatch, findInterval

Examples

x <- c(1.11, 2.22, 3.33, 5.0, 5.1)

bsearch(2.22, x) # 2
bsearch(3.0, x) # NA
bsearch(3.0, x, nearest=TRUE) # 3
bsearch(3.0, x, tol=0.1, tol.ref="values") # 3

y <- c("hello", "world!")
bsearch("world!", y) # 2
bsearch("worl", y) # NA
bsearch("worl", y, nearest=TRUE) # 2

Example output

sh: 1: cannot create /dev/null: Permission denied
Loading required package: BiocParallel
Loading required package: Matrix
Loading required package: biglm
Loading required package: DBI

Attaching package: ‘matter’

The following object is masked from ‘package:biglm’:

    biglm

The following objects are masked from ‘package:base’:

    apply, scale

[1] 2
[1] NA
[1] 3
[1] 3
[1] 2
[1] NA
[1] 2

matter documentation built on Nov. 8, 2020, 6:15 p.m.