# FindFirstFunctions

FindFirstFunctions.jl is a package for faster `findfirst`

type functions. These are specailized to improve performance
over more generic implementations.

## Functions

`findfirstequal`

findfirstequal(x::Int64,A::DenseVector{Int64})

Finds the first value in `A`

equal to `x`

`bracketstrictlymontonic`

bracketstrictlymontonic(v, x, guess; lt=<comparison>, by=<transform>, rev=false)

Starting from an initial `guess`

index, find indices `(lo, hi)`

such that `v[lo] ≤ x ≤ v[hi]`

according to the specified order, assuming that `x`

is actually within the range of
values found in `v`

. If `x`

is outside that range, either `lo`

will be `firstindex(v)`

or
`hi`

will be `lastindex(v)`

.

Note that the results will not typically satisfy `lo ≤ guess ≤ hi`

. If `x`

is precisely
equal to a value that is not unique in the input `v`

, there is no guarantee that `(lo, hi)`

will encompass *all* indices corresponding to that value.

This algorithm is essentially an expanding binary search, which can be used as a precursor
to `searchsorted`

and related functions, which can take `lo`

and `hi`

as arguments. The
purpose of using this function first would be to accelerate convergence in those functions
by using correlated `guess`

es for repeated calls. The best `guess`

for the next call of
this function would be the index returned by the previous call to `searchsorted`

.

See `sort!`

for an explanation of the keyword arguments `by`

, `lt`

and `rev`

.

`searchsortedfirstcorrelated(v::AbstractVector, x, guess)`

searchsortedfirstcorrelated(v::AbstractVector{T}, x, guess::T)

An accelerated `findfirst`

on sorted vectors using a bracketed search. Requires a `guess`

to start the search from.

Some benchmarks:

julia> x = rand(Int, 2048); s = sort(x);
julia> @btime findfirst(==($x[1011]), $x)
266.427 ns (0 allocations: 0 bytes)
1011
julia> @btime FindFirstFunctions.findfirstequal($x[1011], $x)
67.502 ns (0 allocations: 0 bytes)
1011
julia> @btime searchsortedfirst($s, $s[1011])
8.897 ns (0 allocations: 0 bytes)
1011
julia> @btime FindFirstFunctions.findfirstsortedequal($s[1011], $s)
10.896 ns (0 allocations: 0 bytes)
1011