# How to searchsortedfirst when each element requires expensive transformation

**URL:** <https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720>\
**Category:** Performance\
**Created:** [September 16, 2020, 5:31pm UTC](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720 "2020-09-16T17:31:28Z")\
**Posts on this page:** 5\
**Page:** 2

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 17, 2020, 5:48pm UTC](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720/21 "2020-09-17T17:48:14Z")

</div>

> [@lmiq](#):
>
> `m = trunc(Int64,(hi+lo)/2)`

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😉

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 17, 2020, 6:18pm UTC](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720/22 "2020-09-17T18:18:00Z")

</div>

In base this implemented as:

```julia
# 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.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 17, 2020, 8:13pm UTC](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720/23 "2020-09-17T20:13:01Z")

</div>

> [@lmiq](#):
>
> since the slow part of the code would be computation of the `expensive` function, the time required by the search itself is not important

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.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 17, 2020, 8:47pm UTC](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720/24 "2020-09-17T20:47:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [September 17, 2020, 8:49pm UTC](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720/25 "2020-09-17T20:49:40Z")

</div>

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

```julia
julia> (5+3) ÷ 2
4

```

[Previous page](https://discourse.julialang.org/t/how-to-searchsortedfirst-when-each-element-requires-expensive-transformation/46720.md?page=1)