How to searchsortedfirst when each element requires expensive transformation

As far as I can tell, this is just div(hi + lo, 2), only slower, since hi and lo are always positive.

It’s better to just directly do integer division (in this case just a bit shift), than first doing a float division and then convert to integer again. Shorter too😉


In base this implemented as:

# This implementation of `midpoint` is performance-optimized but safe
# only if `lo <= hi`.
midpoint(lo::T, hi::T) where T<:Integer = lo + ((hi - lo) >>> 0x01)
midpoint(lo::Integer, hi::Integer) = midpoint(promote(lo, hi)...)

Yet in this case I was intentionally using only things I knew by heart, to see how efficient that could get. In this case, since the slow part of the code would be computation of the expensive function, the time required by the search itself is not important whenever no additional functional evaluations are made.

But your suggestion is indeed important if the function f was cheap (for ex. f(x) = x+1). In this case it doubles the speed of the search for the example above, and the “custom” implementation becomes as fast as the intrinsic function with the new type.

1 Like

Yeah, it’s not important, I just have a hard time watching something inefficient, when it’s not even briefer or simpler or more elegant :grin: Using div is better along every dimension, and I also often see posters doing exactly this kind of ‘float division + conversion’, so I have a knee-jerk reaction.


Effectively, I was not aware of ‘div’. I will update my actual packages to use that.

div has the unicode infix form ÷ (typed by \div+tab) which is pretty nice!

julia> (5+3) ÷ 2
1 Like