arrays - 中的排序版本

我有一个时间数组event_times，我想检查t in event_times。但是，我知道event_times已排序。有没有办法利用它来加快搜索速度？

最佳答案

朱利安惯用的方式是:

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))

然后:

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

如果我没记错的话，David Sanders就有一个使用此名称的实现。也许查看https://github.com/JuliaIntervals/IntervalOptimisation.jl/blob/889bf43e8a514e696869baaa6af1300ace87b90b/src/SortedVectors.jl会促进重用。