Juliaのsearchsorted関数について

Juliaでsearchsorted関数を使う機会があったのですが、[Juliaの公式document](https://docs.julialang.org/en/v1/base/sort/#Base.Sort.searchsorted)の説明が結構分かりにくかったので色々調べてみました。

# `searchsorted`関数

Pythonにも同じ機能のライブラリや関数、例えば[bisectライブラリ](https://docs.python.org/ja/3/library/bisect.html?highlight=bisect#module-bisect )(nagataaaasさんに教えてもらいました)や[searchsorted関数(numpy)](https://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html)はあるのですが、Juliaでは引数が異なってたりするので注意が必要です。Pythonでは`searchsorted`関数は一次元arrayと実数(もしくはそれから成る一次元array)を引数にとります。この関数はざっくりいうと、その実数に最も近いarrayの要素のインデックスを返すというものです。

Juliaには`searchsorted`の他に`searchsortedfirst`と`searchdortedlast`という２つの関数があります。

基本的に引数は　次のようになっています。

~~~Julia
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
~~~
`a`は`AbstractVector`型でサーチ対象の一次元Array、`x`は`Real`型でソートするための実数（Pythonとは異なり一次元配列は引数にできません）。キーワード引数は`by`、`lt`、`rev`となっています。

基本的に配列`a`は昇順・降順でソート済みであることを前提とします。ソートしてない場合は`sort`もしくは`sort!`を使いましょう。

## `searchsortedfirst`関数

`searchsortedfirst`は

```math
a[i-1] < x \le a[i]
```
を満たす最小の i を返します。また、`x`が`a`の中の全要素より大きい時は`length(a)+1`を返します。

~~~Julia
julia> searchsortedfirst([1,3,5,7], 4)
3

julia> searchsortedfirst([1,3,5,7], 9)
5
~~~

配列`a`が降順の時はキーワード引数の`rev`をtrueにします。このとき

```math
a[i-1] > x \ge a[i]
```
となる最小のiを返します。

~~~Julia
julia> searchsortedfirst([7,5,3,1], 4, rev=true)
3
~~~
となります。


## `searchsortedlast`関数

`searchsortedlast`は

```math
a[i] \le x < a[i+1]
```
を満たす最小の i を返します。また、`x`が`a`の中の全要素より小さい時は0を返します。

~~~Julia
julia> searchsortedlast([1,3,5,7], 4)
2

julia> searchsortedlast([1,3,5,7], -1)
0
~~~

同様に降順のときはキーワード引数の`rev`をtrueにします。このとき

```math
a[i] \ge x > a[i+1]
```
となる最大のiを返します。

~~~Julia
julia> searchsortedlast([7,5,3,1], 4, rev=true)
0
~~~
となります。


## `searchsorted`関数

さて最初に戻って`searchsorted`関数を見てみましょう。

~~~Julia
julia> searchsorted([1,3,5,7],4)
3:2

julia> typeof(searchsorted([1,3,5,7],4))
UnitRange{Int64}
~~~

`searchsorted`の返り値の型は`UnitRange{Int64}`になっています（マシンによっては`UnitRange{Int32}`になるかもしれません）。`UnitRange`はよくfor文などで使用される`1:10`などの型です。
ちなみに`UnitRange`は

~~~Julia
struct UnitRange{T<:Real} <: AbstractUnitRange{T}
     start::T
     stop::T
     UnitRange{T}(start, stop) where {T<:Real} = new(start,unitrange_last(start,stop))
end
~~~
で型が作られているので、先ほどの`3:2`のそれぞれの数字は次のように取得できます。

~~~Julia
julia> searchsorted([1,3,5,7],4).start
3

julia> searchsorted([1,3,5,7],4).stop
2
~~~

ここで気づいた人がいるかもしれませんが、それぞれ`searchsortedfirst`と`searchsortedlast`に対応しています。

~~~Julia
julia> searchsorted([1,3,5,7],4).start == searchsortedfirst([1,3,5,7],4)
true

julia> searchsorted([1,3,5,7],4).stop == searchsortedlast([1,3,5,7],4)
true
~~~

またさらにそれぞれはnumpyの`searchsorted(a,x,side='right')`、`searchsorted(a,x,side='left')`にも対応しています（もちろんPythonの場合インデックスが0から始まるという違いがありますが）。

### キーワード引数`by`

キーワード引数の`by`は配列`a`に対し要素間の比較を行う前に施す関数を指定します。

~~~Julia
#絶対値を見る
julia> searchsortedfirst([1, -2, 4, -10], -3, by=abs)
3

#１番目の要素を見る
julia> searchsortedfirst([(1,"a"), (3,"b"), (5,"g")], (4,"h"), by=x->x[1])
3
~~~


---

最初に述べた通り配列`a`はソート済みであることを仮定していました。これは公式ドキュメントにも書いてある通りです。

>Return the range of indices of a which compare as equal to `x` (using binary search) according to the order specified by the `by`, `lt` and `rev` keywords, **assuming that `a` is already sorted in that order**.

しかし`a`がソートされていなくても`searchsorted`関数は使うことはできます。

~~~Julia
julia> searchsorted([3,1,6,5], 2)
3:2

julia> searchsortedfirst([3,1,6,5], 2)
3

julia> searchsortedlast([3,1,6,5], 2)
2
~~~

~~ですが先の説明に従うと、`searchsortedfirst`では1を返すはずでは？~~

~~とりあえずソートしてない配列を渡すのはやめたほうが良さそうな気がします（そもそもソートしてない配列に対して`searchsorted`を使いたい場面ってあるのかな？）~~

antimon2さんより、`searchsorted関数`は**binary search**を使っているのでこういうことが起こるそう（確かにdocumentに書いてありますね）。なのでかならずソート済みの配列を用いるべきだし、ソートしてない配列にこの関数を使いたい場面などないみたいです（詳しくはantimon2さんのコメントを参照）




(何か間違い等あればコメントお願いします。)