探索とは、目当てを見つけること
探索とは、データの中から目当てのものを見つける手順のことです。代表は、線形探索と二分探索の2つです。
百万件の商品から1つを探すとき、線形探索は最大で百万回見ます。二分探索なら、20回で終わります。ただし二分探索には、守る約束が1つあります。
このレッスンのゴール
メモ
線形探索と二分探索の見る回数を比べて、二分探索に必要な条件を言える。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| 線形探索 | 先頭から1つずつ順に見ていく探し方 | |
| 二分探索 | 真ん中を見て、探す範囲を半分にする探し方 | |
| 整列済み | 小さい順に並んでいること | |
| 範囲 | まだ探していない、候補の部分 | low から high まで |
| 最悪の場合 | 一番ステップ数が多くなる場合 |
学生が入力するセルは、このプレビューでは空白です。
線形探索は端から順に見る
線形探索は、先頭から順に1つずつ見ていきます。目当てが見つかったら止まります。
目当てが先頭にあれば、1回で終わります。最後にあるか、リストにないときは、n 回全部を見ます。だから最悪の場合は n ステップで、増え方は線形です。リストが並んでいなくても使えます。
線形探索で見た回数を数える
# 値段のリストを端から順に見て、目当ての値段を探します。
prices = [100, 150, 200, 250, 300, 350, 400, 450]
target = 350
steps = 0
found = -1
for i in range(len(prices)):
steps = steps + 1
if prices[i] == target:
found = i
break
print("位置:", found, "見た回数:", steps)
# target を 100 や 999 に変えて、回数を見ましょう。
二分探索は真ん中を見て半分にする
二分探索は、整列済みのリストにだけ使えます。真ん中を見て、目当てより小さければ左半分を捨てます。大きければ右半分を捨てます。
これを繰り返すと、範囲は毎回半分になります。16個なら、最大でも5回で終わります。
800円を探す: 4回で見つかる
| 回 | low から high | 真ん中の値段 | 次にすること |
|---|---|---|---|
| 1 | 位置0から15 | 450円 | 小さいので左を捨てる |
| 2 | 位置8から15 | 650円 | 小さいので左を捨てる |
| 3 | 位置12から15 | 750円 | 小さいので左を捨てる |
| 4 | 位置14から15 | 800円 | 見つかった |
学生が入力するセルは、このプレビューでは空白です。
二分探索の動きを見る
# 整列済みのリストの真ん中を見て、範囲を半分にしていきます。
prices = [100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850]
target = 800
low = 0
high = len(prices) - 1
steps = 0
while low <= high:
mid = (low + high) // 2
steps = steps + 1
print("見た位置:", mid, "値段:", prices[mid])
if prices[mid] == target:
break
elif prices[mid] < target:
low = mid + 1
else:
high = mid - 1
print("見た回数:", steps)
# target を 100 に変えて実行しましょう。
よくある間違い
注意
二分探索はどんなリストでも速い、と思いがちです。真ん中を見て半分を捨てられるのは、並んでいるときだけです。並んでいないリストでは、捨てた半分に目当てがあるかもしれません。先に整列するか、線形探索を使います。
ラボの端末で整列済みを確かめる
下の Run で、ラボの端末に整列のコマンドを打ちます。sort -n は数の小さい順に並べ、paste は1行にまとめます。
最後の Run は、Python の bisect に位置を聞きます。Python 自身も、二分探索を使っています。
小さい順に並べる
printf '%s\n' 40 7 19 3 | sort -n | paste -sd' 'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
二分探索で位置を聞く
python3 -c "import bisect; print(bisect.bisect_left([3, 7, 19, 40], 19))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
百万件の最悪の回数
python3 -c "import math; print(math.floor(math.log2(1000000)) + 1)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: 並べてから探す
並んでいないリストを、1回だけ探すなら、線形探索が得です。整列にも手数がかかるからです。
同じリストを1000回探すなら、どうでしょう。先に1回整列して、二分探索を1000回使う方が得な理由を、自分の言葉で説明しましょう。