二分探索
データに対する検索を行うにあたって、データを頭から順番に探索していく方法は一般に効率が悪いことが知られています。
ソート（整列）済みのリストに入ったデータに対する検索を行う場合には、二分探索という方法があります。二分探索では、探索範囲の中央の値を見て、検索したい値がその右側に存在するか左側に存在するかを判断し、存在しそうな範囲を次の探索範囲とすることを繰り返します。
課題４５：二分探索
長さ $n$ の単調非減少な数列 $a_0, a_1, ..., a_{n-1}$ と、実数 $k$ を入力したとき、$a_i$ ≥ $k$ となるような最小の $i$ を返す関数を、二分探索アルゴリズムに基づいて作ってください。そのような $i$ が存在しない場合には $n$ を返すようにしてください。
ただし、
- 1 ≤ $n$ ≤ 106
- 0 ≤ $a_1$ ≤ $a_2$ ≤ ... ≤ $a_n$ ≤ 109
- 0 ≤ $k$ ≤ 109
とします。
- 例1
n = 8
a = [3, 4, 4, 4, 7, 9, 10, 10]
k = 8
5
- 例2
n = 8
a = [3, 4, 4, 4, 7, 9, 10, 10]
k = 4
1
- 例3
n = 8
a = [3, 4, 4, 4, 7, 9, 10, 10]
k = 0
0
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。