# findInterval {base}

### Description

Given a vector of non-decreasing breakpoints in `vec`

, find the interval containing each element of `x`

; i.e., if `i <- findInterval(x,v)`

, for each index `j`

in `x`

v[i[j]] ≤ x[j] < v[i[j] + 1] where v[0] := - Inf, v[N+1] := + Inf, and `N <- length(v)`

. At the two boundaries, the returned index may differ by 1, depending on the optional arguments `rightmost.closed`

and `all.inside`

.

### Usage

findInterval(x, vec, rightmost.closed = FALSE, all.inside = FALSE)

### Arguments

- x
- numeric.
- vec
- numeric, sorted (weakly) increasingly, of length
`N`

, say. - rightmost.closed
- logical; if true, the rightmost interval,
`vec[N-1] .. vec[N]`

is treated as*closed*, see below. - all.inside
- logical; if true, the returned indices are coerced into
`1,...,N-1`

, i.e.,`1`

and`N`

to`N-1`

.

### Details

The function `findInterval`

finds the index of one vector `x`

in another, `vec`

, where the latter must be non-decreasing. Where this is trivial, equivalent to `apply( outer(x, vec, ">="), 1, sum)`

, as a matter of fact, the internal algorithm uses interval search ensuring O(n * log(N)) complexity where `n <- length(x)`

(and `N <- length(vec)`

). For (almost) sorted `x`

, it will be even faster, basically O(n).

This is the same computation as for the empirical distribution function, and indeed, `findInterval(t, sort(X))`

is *identical* to where Fn is the empirical distribution function of X[1],..,X[n].

When `rightmost.closed = TRUE`

, the result for `x[j] = vec[N]`

( = max(vec)), is `N - 1`

as for all other values in the last interval.

### Values

vector of length `length(x)`

with values in `0:N`

(and `NA`

) where `N <- length(vec)`

, or values coerced to `1:(N-1)`

if and only if `all.inside = TRUE`

(equivalently coercing all x values *inside* the intervals). Note that `NA`

s are propagated from `x`

, and `Inf`

values are allowed in both `x`

and `vec`

.

### See Also

`approx(*, method = "constant")`

which is a generalization of `findInterval()`

, `ecdf`

for computing the empirical distribution function which is (up to a factor of n) also basically the same as `findInterval(.)`

.

### Examples

Documentation reproduced from R 3.0.2. License: GPL-2.