# Searchsorted by attribute

**URL:** <https://discourse.julialang.org/t/searchsorted-by-attribute/107754>\
**Category:** General Usage\
**Tags:** question\
**Created:** [December 18, 2023, 4:29am UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754 "2023-12-18T04:29:09Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![goerz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerz/32/3269_2.png) [@goerz](https://discourse.julialang.org/u/goerz)\
**Post date:** [December 18, 2023, 4:29am UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754/1 "2023-12-18T04:29:09Z")

</div>

Suppose I have an array `inventory::Vector{InventoryObject}` that is sorted by the `name` attribute of each element (`sort` with `by=(obj->obj.name)`)

The `InventoryObject` is defined as

```julia
@kwdef struct InventoryObject
    name::String
    domain::String = "jl"
    role::String
    priority::Int64 = 1
    uri::String
    dispname::String = "-"
end

```

Is there some way to use [`searchsorted`](https://docs.julialang.org/en/v1/base/sort/#Base.Sort.searchsorted) to find the range of indices for elements with a given `x=name`? I’m not sure I really understand the `by` and `lt` arguments to `searchsorted`, but they don’t seem to be completely helpful here. I’m missing a way to apply a transformation to each element of `inventory` before comparing to the search value `x`.

The only idea I’ve been able to come up with so far is to define a view like

```julia
struct InventoryNameView <: AbstractArray{Int, 1}
    inventory::Vector{InventoryObject}
end

Base.size(view:: InventoryNameView) = size(view.inventory)
Base.getindex(view:: InventoryNameView, i::Int) = view.inventory[i].name

```

and call `searchsorted` on the `InventoryNameView`. Did I overlook something?

P.S.: I’d prefer to do this without adding new dependencies, with standard-library functions only.

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [December 18, 2023, 4:59am UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754/2 "2023-12-18T04:59:23Z")

</div>

Isn’t it just `searchsorted(xs, x, by=x->x.name)`?

---

<div class="post-metadata">

**Author:** ![goerz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerz/32/3269_2.png) [@goerz](https://discourse.julialang.org/u/goerz)\
**Post date:** [December 18, 2023, 5:15am UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754/3 "2023-12-18T05:15:56Z")

</div>

No, the `by` would get applied to `x` as well, as far as I can tell:

```julia
julia> inventory = [
       InventoryObject(name="a", role="any", uri="-"),
       InventoryObject(name="b", role="any", uri="-"),
       InventoryObject(name="b", role="func", uri="-"),
       InventoryObject(name="b", role="macro", uri="-"),
       InventoryObject(name="c", role="any", uri="-")
       ]

julia> searchsorted(inventory, "b"; by=(x -> x.name))
ERROR: type String has no field name

```

To be fair, my initial intuition also was that this should work. The documentation of `searchsorted` isn’t exactly clear on this, so this error might even be a bug.

---

<div class="post-metadata">

**Author:** ![goerz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerz/32/3269_2.png) [@goerz](https://discourse.julialang.org/u/goerz)\
**Post date:** [December 18, 2023, 5:17am UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754/4 "2023-12-18T05:17:39Z")

</div>

Oh, actually, this might work:

```julia
julia> searchsorted(inventory, InventoryObject(name="b", role="", uri=""); by=(x -> x.name))
2:4

```

So does this:

```julia
julia> struct DummyValue
       name::String
       end

julia> searchsorted(inventory, DummyValue("b"); by=(x -> x.name))
2:4

```

Although I’m not sure it’s exactly elegant.

It also means that strictly speaking, the docstring of `searchsorted` is lying when it says “Return the range of indices of `a` which compare as equal to `x`”, since the values in the returned range clearly do not compare as equal to `x`!

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [December 18, 2023, 5:53am UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754/5 "2023-12-18T05:53:14Z")

</div>

cc @Lilith

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [December 18, 2023, 2:29pm UTC](https://discourse.julialang.org/t/searchsorted-by-attribute/107754/6 "2023-12-18T14:29:02Z")

</div>

Jeremie Knuesel (@knuesel on gihub) fixed the docstring to accurately document this behavior in [https://github.com/JuliaLang/julia/pull/48387](https://github.com/JuliaLang/julia/pull/48387). In 1.10, the docstring reads

```julia
help?> searchsorted
search: searchsorted searchsortedlast searchsortedfirst

  searchsorted(v, x; by=identity, lt=isless, rev=false)

  Return the range of indices in v where values are equivalent to x, or an
  empty range located at the insertion point if v does not contain values
  equivalent to x. The vector v must be sorted according to the order defined
  by the keywords. Refer to sort! for the meaning of the keywords and the
  definition of equivalence. Note that the by function is applied to the
  searched value x as well as the values in v.

  The range is generally found using binary search, but there are optimized
  implementations for some inputs.

  See also: searchsortedfirst, sort!, insorted, findall.

  Examples
  ≡≡≡≡≡≡≡≡

  julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
  3:3
  
  julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
  4:5
  
  julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
  3:2
  
  julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
  7:6
  
  julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
  1:0
  
  julia> searchsorted([1=>"one", 2=>"two", 2=>"two", 4=>"four"], 2=>"two", by=first) # compare the keys of the pairs
  2:3

```

The existing comparison archetecture does not support the notion of an opject that the `by` function has already been applied to. However, this could become possible after [Use shared pre-computation for `by` and `perm` orderings. by LilithHafner · Pull Request #52033 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/52033).