連絡先から一人を探す
スマホの連絡先に300人が入っています。「田中さん」に電話したいとき、一人ずつ上から読む人はいません。
探し方には、いくつかの手順があります。手順が違うと、同じデータでも、見る回数が大きく変わります。
このレッスンのゴール
メモ
線形探索と二分探索で、リストから値を探せる。
重要な言葉
| ことば | いみ |
|---|---|
| アルゴリズム | 問題を解くための、決まった手順 |
| 線形探索 | 先頭から一つずつ順に調べる探し方 |
| 二分探索 | 真ん中を見て、候補を半分ずつ捨てる探し方 |
| 整列済み | 小さい順などに、すでに並んでいること |
| 比較 | 探している値と、リストの値を見比べること |
学生が入力するセルは、このプレビューでは空白です。
線形探索は先頭から順に見る
線形探索は、リストの先頭から一つずつ、探す値と見比べます。見つかったら止まります。
最後まで見つからなければ「ない」と答えます。リストが整列していなくても使えるのが強みです。
例：42を探す手順
| 何回目 | 見る値 | 42と同じか |
|---|---|---|
| 1 | 8 | いいえ |
| 2 | 15 | いいえ |
| 3 | 21 | いいえ |
| 4 | 34 | いいえ |
| 5 | 42 | はい、見つかった |
学生が入力するセルは、このプレビューでは空白です。
線形探索のプログラム
numbers = [8, 15, 21, 34, 42, 57, 63, 70]
def linear_search(items, target):
for position in range(len(items)):
# 一つ見るたびに比較を一回する
if items[position] == target:
return position
return -1
# 42 は先頭から数えて5番目なので、位置は 4 になる
print(linear_search(numbers, 42))
# 99 はリストにないので、-1 になる
print(linear_search(numbers, 99))
二分探索は半分ずつ捨てる
辞書で言葉を引くとき、最初のページから読む人はいません。真ん中あたりを開き、探す言葉が前か後かを決めます。
二分探索も同じです。真ん中の値を見て、探す値が小さければ前半、大きければ後半だけを残します。これを繰り返します。
例：21を二分探索で探す
| 何回目 | 範囲の位置 | 真ん中の値 | 次にすること |
|---|---|---|---|
| 1 | 0 から 7 | 34 | 21は小さいので、前半を残す |
| 2 | 0 から 2 | 15 | 21は大きいので、後半を残す |
| 3 | 2 から 2 | 21 | 見つかった |
学生が入力するセルは、このプレビューでは空白です。
二分探索は整列済みだけに使える
真ん中より小さければ前半にある、と言えるのは、リストが小さい順に並んでいるからです。
並んでいないリストで半分を捨てると、探す値まで捨ててしまいます。先に整列するか、線形探索を使います。
よくある間違い
注意
二分探索のほうが速いので、いつでも使えると考えがちです。二分探索は、リストが整列済みのときだけ正しく動きます。並んでいないリストには、線形探索を使います。
ラボのデータで確かめる
ラボの hires.csv には、2025年の自転車の貸し出しが、1日1行で入っています。日付は古い順に並んでいるので、整列済みです。
次の実行で、行の数と、最初と最後の日付を確かめます。見るだけで、ファイルは変わりません。
データの行の数を数える
docker exec jupyter python3 -c 'print(len(open("hires.csv").readlines()) - 1)'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
最後の日付を見る
docker exec jupyter python3 -c 'print(open("hires.csv").readlines()[-1].split(",")[0])'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
365行を探す回数
一つ目の実行は 365 と出ます。線形探索で最後の日を探すと、比較は365回です。
二分探索は、一回で半分に減ります。365行なら、多くても9回で見つかります。次の実行で、その9を計算で確かめます。
二分探索の最大回数を計算する
docker exec jupyter python3 -c 'print(int(__import__("math").log2(365)) + 1)'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例：データが増えたときの最大回数
| データの数 | 線形探索 | 二分探索 |
|---|---|---|
| 10 | 10回 | 4回 |
| 365 | 365回 | 9回 |
| 1000 | 1000回 | 10回 |
| 1000000 | 1000000回 | 20回 |
学生が入力するセルは、このプレビューでは空白です。