O(1) searchsorted for Ranges satisfying RangeStepRegular

[kcajf]

RangeStepStyle is defined here:
https://github.com/JuliaLang/julia/blob/master/base/traits.jl#L55

Presumably, the implication of this is that searchsorted on a RangeStepRegular Range should be constant-time: just subtract the start, divide by the step, and round it (of course, handling all the edge-cases)? Is this something that could/should be implemented somewhere central? If so, I can't really work out how to write a method that dispatches specifically on Ranges that implement RangeStepRegular.

[kcajf]

Looks like this is already implemented in Base for AbstractRange{<:Real}, so there is a base to work off / extend:

julia/base/sort.jl

Line 224 in 6175bd9

function searchsortedlast(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering)

[nalimilan]

The RangeStepStyle trait isn't used anywhere currently. It should probably have been removed when #26022 got rid of its uses in hashing code (at least the docstrings should be updated to stop mentioning hash). Maybe we could use it for searchsorted, but you could also start implementing functions for specific range types with a know regular step -- I'm not sure whether it's possible to write generic code which would work for any regular range.

[mcabbott]

Just found this issue, wonder whether this trait ought to have been used by #30778 to avoid #35203?