部品番号20316はありますか
愛知県の自動車部品メーカーで、取引先から電話が来ました。「部品番号20316の在庫はありますか」。
在庫の一覧には、何万もの部品番号があります。上から一つずつ見ていたら、相手を待たせてしまいます。
でも、一覧は番号の小さい順に並んでいます。並んでいれば、もっと速く探せます。
このレッスンのゴール
メモ
線形探索と二分探索で、項目を見つけることができる。
キーワード
| ことば | いみ |
|---|---|
| アルゴリズム | 問題を解くための手順です。 |
| 線形探索 | 前から一つずつ比べて探す方法です。 |
| 整列済み | 小さい順などに並んでいる状態です。 |
| 二分探索 | 真ん中を見て、半分を捨てながら探す方法です。 |
| -1 | 「見つからない」を表す約束の値です。 |
学生が入力するセルは、このプレビューでは空白です。
線形探索は前から順番に比べる
線形探索は、最初の要素から順番に、探している値と比べます。
見つかったら止まります。最後まで見てもなければ、-1 を返します。
並んでいないリストにも使えるのが長所です。ただし、最悪の場合は全部を見ます。5万件なら、5万回比べます。
やってみよう: ロット番号を探す
# 今週、検査に回ってきた部品のロット番号です。順番はばらばらです。
lots = ["L-5521", "L-1180", "L-9034", "L-2716", "L-6403"]
target = "L-2716"
steps = 0
found_at = -1
for i in range(len(lots)):
steps = steps + 1
if lots[i] == target:
found_at = i
break # 見つかったので、残りは見なくてよい
print("場所:", found_at, " 比べた回数:", steps)
# target を、リストにない "L-0000" に変えて、比べた回数を見ましょう。
二分探索は半分ずつ捨てる
二分探索は、整列済みのリストにだけ使えます。まず真ん中の要素を見ます。
探す値より小さければ、左半分を全部捨てます。大きければ、右半分を捨てます。
残った半分で、同じことをくり返します。一回比べるごとに、探す範囲が半分になります。
やってみよう: 部品番号を探す
# 部品番号の一覧です。小さい順に並んでいます。
parts = [20110, 20135, 20162, 20188, 20204, 20231, 20257, 20290, 20316, 20342, 20375]
target = 20316
low = 0
high = len(parts) - 1
steps = 0
while low <= high:
steps = steps + 1
middle = (low + high) // 2
print(steps, "回目: インデックス", middle, "を見る =", parts[middle])
if parts[middle] == target:
print("見つかりました。インデックス", middle)
break
elif parts[middle] < target:
low = middle + 1 # 探す番号は右半分にある
else:
high = middle - 1 # 探す番号は左半分にある
# target を 20110 や 20375 に変えて、何回で見つかるか数えましょう。
例: 11個の中から20316を探す
| 回目 | low | high | middle | 真ん中の値 | 判断 |
|---|---|---|---|---|---|
| 1 | 0 | 10 | 5 | 20231 | 20316の方が大きいので右へ |
| 2 | 6 | 10 | 8 | 20316 | 見つかった |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
「二分探索は、どんなリストにも使える」と思う人がいます。並んでいないリストでは、探す値がある側の半分を捨ててしまうことがあります。すると、値があるのに -1 が返ります。使う前に、整列済みか確かめましょう。
例: 最悪の場合に比べる回数
| 要素の数 | 線形探索(最大) | 二分探索(最大) |
|---|---|---|
| 11 | 11回 | 4回 |
| 1,000 | 1,000回 | 10回 |
| 100万 | 100万回 | 20回 |
学生が入力するセルは、このプレビューでは空白です。