# 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😉

2 Likes

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

3 Likes

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
4
``````
1 Like