はじめに
数学者であり、シンガーソングライターでもある人たちのグループに、偶然出会いました。彼らは、お気に入りの数それぞれのために歌を書いています。そして、ご想像のとおり、お気に入りの数はたくさんあります（0や73、6174など）。
お気に入りの数の歌を聴いてみたくなりましたが、あまりに多くの歌を聴き進めなければならないので、目当ての歌を見つけるにはしばらく時間がかかりそうです。幸いなことに、彼らは歌をプレイリストにまとめ、タイトル順に並べています。タイトルとは、その歌が歌っている数そのものです。
タイトルさえわかっていれば、二分探索アルゴリズムを使って歌をすばやく見つけられることに気づきます。
説明
二分探索アルゴリズムを実装してください。
二分探索アルゴリズムは、配列を半分に分割することを繰り返し、探している値が含まれる半分だけを残すことで、配列の中から目的の値を見つけ出します。
これにより、目的の値が見つかるまで、あるいは候補となる場所がすべてなくなるまで、その値がありうる場所をすばやく絞り込んでいけます。
二分探索は、配列がソートされているときにだけ使えます。
アルゴリズムは次のようなものです。
- _ソート済み_の配列の中央にある要素を見つけ、探している値と比べます。
- 中央の要素が探している値そのものであれば、それでおしまいです！
- 中央の要素が探している値より大きければ、その要素と、それより後ろにあるすべての要素を除外できます。
- 中央の要素が探している値より小さければ、その要素と、それより前にあるすべての要素を除外できます。
- 配列のすべての要素が除外されたなら、探している値は配列の中にありません。
- そうでなければ、まだ除外されていない部分の配列に対して同じ処理を繰り返します。
例を見てみましょう。
次のソート済みの配列から、数値23を探すとしましょう：[4, 8, 12, 16, 23, 28, 32]。
- まず、23を中央の要素である16と比べます。
- 23は16より大きいので、配列の左半分を除外でき、
[23, 28, 32]が残ります。
- 次に、23を新しい中央の要素である28と比べます。
- 23は28より小さいので、配列の右半分を除外できます：
[23]。
- 目的の値が見つかりました。
振る舞い
解答は、テストケースに対して、Juliaの組み込みsearchsorted関数と同じ振る舞いをする必要があります。これはつまり、配列内で最初に見つけた一致する要素のインデックスを返すのではなく、配列内の最初の一致する要素のインデックスを下限、最後の一致する要素のインデックスを上限とする範囲を返すということです。ただし、解答を簡単にするために、対象の要素が繰り返されていないと仮定してもかまいません。ただし、複数一致のボーナスタスクのテストセットは例外です。
探している項目が配列にない場合は、その項目をソート済みの配列に挿入できるインデックスを下限とする空の範囲を返さなければなりません。空の範囲とは、上限が下限より小さい範囲のことです。
詳細については、searchsorted関数のドキュメントと例をお読みください。
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
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.
Return an empty range located at the insertion point if a does not contain
values equal to x.
See also: insorted, searchsortedfirst, sort, 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
ボーナスタスク
- 解答を拡張して、キーワード引数
by・lt・revをサポートするようにしましょう。byは配列のすべての要素に適用される変換を指定し、ltは比較を指定し、revは配列が逆順に並んでいるかどうかを指定します。これらのパラメーターを使用する場合、配列はすでにこれらのパラメーターでソートされていると仮定しなければなりません。詳細はsortのドキュメントを参照してください。
- 対象の要素が繰り返されている配列をサポートしてください（対象の要素と等しいと比較される最初と最後のインデックスを探します）。
