Sorted version of in

Question

I have an array of times event_times and I want to check if t in event_times. However, I know that event_times is sorted. Is there a way to make use of that to make the search faster?

Answer 1

An idiomatic Julian way would be an elaboration of:

struct SortedVector{T,V<:AbstractVector} <: AbstractVector{T}
    v::V
    SortedVector{T,V}(v::AbstractVector{T}) where {T, V} = new(v)
    # check sorted in inner constructor??
end
SortedVector(v::AbstractVector{T}) where T = SortedVector{T,typeof(v)}(v)

@inline Base.size(sv::SortedVector) = size(sv.v)
@inline Base.getindex(sv::SortedVector,i) = sv.v[i]
@inline Base.in(e::T,sv::SortedVector{T}) where T = !isempty(searchsorted(sv.v,e))

And then:

julia> v = SortedVector(sort(rand(1:10,10)))
10-element SortedVector{Int64,Array{Int64,1}}:
  1
  4
  5
  5
  6
  6
  6
  7
  7
 10

julia> 3 in v
false

julia> 1 in v
true

If I recall correctly David Sanders had an implementation with this name. Perhaps looking at https://github.com/JuliaIntervals/IntervalOptimisation.jl/blob/889bf43e8a514e696869baaa6af1300ace87b90b/src/SortedVectors.jl would promote reuse.

Answer 2

Following @ColinTBowers's hint, you can use the fact that searchsorted returns a range which is empty iff t is not in event_times. Thus !isempty(searchsorted(event_times,t)) is a fast method to get the answer.