Juliaの二分探索関数

Juliaには二分探索(binary search)を行う関数 insorted、 searchsortedfirst、searchsortedlast、searchsortedがありますが、戻り値の意味をよく忘れてしまうので備忘録としてまとめます。

insorted

x が a 中に存在すれば true、存在しなければ falseを返す。

例

julia> insorted([1, 3, 3, 5, 7, 9], 3)
true

julia> insorted([1, 3, 3, 5, 7, 9], 4)
false

searchsortedfirst

searchsortedfirst(a, x) は a[i] $\ge$ x となる最小の i を返す。
もし、x が a のすべての値より大きければ lastindex(a) + 1 を返す。

要するに「x 未満にならない最小のインデックスを返す」

ちなみに、xをaに追加するときに、この関数の戻り値 i を使って insert!(a, i, x) とすれば a はソートされた状態を維持できる。

例

julia> searchsortedfirst([1, 3, 3, 5, 7, 9], 3)
2  # 3未満にならない最小のインデックスは2

julia> searchsortedfirst([1, 3, 3, 5, 7, 9], 4)
4  # 4未満にならない最小のインデックスは4

julia> searchsortedfirst([1, 3, 3, 5, 7, 9], 10)ｎ
7  # 10未満にならないインデックスは存在しないので、lastindex(a) + 1

searchsortedlast

searchsortedfirst(a, x) は a[i] $\le$ x となる最小の i を返す。
もし、x が a のすべての値より大きければ firstindex(a) - 1 を返す。

要するに 「x を超えない最大のインデックスを返す」

例

julia> searchsortedlast([1, 3, 3, 5, 7, 9], 3)  
3  # 3を超えない最大のインデックスは3

julia> searchsortedlast([1, 3, 3, 5, 7, 9], 4)  
3  # 4を超えない最大のインデックスは3

julia> searchsortedlast([1, 3, 3, 5, 7, 9], -1)
0  # -1を超えないインデックスは存在しないので、firstindex(a) - 1

searchsorted

searchordered(a, x) は a 中の x の範囲を返す。
x が a に存在しない場合は x の挿入位置を示す空の range を返す。

要するに「start が searchsortedfirst(a, x)、stop が searchsortedlast(a, x) の range を返す」

julia> searchsorted([1, 3, 3, 5, 7, 9], 5)
4:4  # 5はインデックス4にのみ存在

julia> searchsorted([1, 3, 3, 5, 7, 9], 3)
2:3  # 3はインデックス2~3に存在

julia> searchsorted([1, 3, 3, 5, 7, 9], 4)
4:3  # 4は存在しない。挿入位置は4なので空のrange 4:3