探索のアルゴリズム｜高校情報Ⅰ

0. どういうまとまりか

たくさんのデータの中から、目的の値がどこにあるか（あるかないか）を探すのが探索です。
代表的なやり方が 2 つあり、データが整列しているかどうかで使えるものが分かれます。

	線形探索	二分探索
やり方	先頭から順に 1 つずつ比べる	中央の値と比べ、探す範囲を半分に絞る
前提	なし（並びは問わない）	データが整列済み
比較回数の最大（データ n 個）	n 回	約 $lo g_{2} n$ 回
データが 2 倍になると	最大の比較回数も 2 倍	最大の比較回数は 1 回増えるだけ

分かれ目は次の 3 つ。

二分探索は、データが大きさの順に並んでいないと使えない。
線形探索の比較回数は最大 n 回、平均でおよそ n/2 回。
二分探索は 1 回比べるごとに範囲が半分になるので、比較回数は約 $lo g_{2} n$ 回。

1. 線形探索

根拠: 学習指導要領情報Ⅰ-(3)-ア-(イ)

線形探索は、配列の先頭から順に、目的の値と等しいかを 1 つずつ調べます。
見つかった時点で終わり、最後まで見つからなければ「無い」と分かります。

線形探索（逐次探索）は、どうやって値を探すか？

先頭から順に 1 つずつ、目的の値と等しいか比べていく

見つかったらそこで終える。データの並び方を問わない。

n 個のデータを線形探索するとき、比較回数の最大は？

n 回

目的の値が最後にあるとき、または無いとき。平均するとおよそ n/2 回。

2. 二分探索

根拠: 学習指導要領情報Ⅰ-(3)-ア-(イ)

二分探索は、探す範囲の中央の値と目的の値を比べ、目的の値が中央より小さければ前半、
大きければ後半だけを残して、同じことを繰り返します。範囲が空になれば「無い」と分かります。

二分探索を使うための前提は？

データが大きさの順に整列していること

整列していないと、中央と比べても、目的の値が前半・後半のどちらにあるか決められない。

二分探索では、中央の値と目的の値を比べたあと、どうするか？

等しければ終了。目的の値のほうが小さければ前半、大きければ後半に範囲を絞って繰り返す

1 回の比較で、探す範囲がおよそ半分になる。

二分探索で、探す範囲の左端の添字が lo、右端が hi のとき、中央の添字はどう求めるか？

(lo + hi) // 2（2 で割った商）

添字は整数でなければならないので、/ ではなく // を使う。

n 個のデータを二分探索するとき、比較回数の最大はおよそいくつか？

約 $lo g_{2} n$ 回

n が 1000 なら 10 回ほど（2 を 10 回かけると 1024）。線形探索の最大 1000 回と大きく違う。

データの数が 2 倍になると、二分探索の最大の比較回数はどう変わるか？

1 回増えるだけ

最初の 1 回の比較で範囲が半分になり、もとの大きさに戻るため。線形探索なら最大の比較回数も 2 倍になる。

3. 使い分けと番兵

根拠: 学習指導要領情報Ⅰ-(3)-ア-(イ)

二分探索は速い代わりに、先に整列しておく手間がかかります。
1 回だけ探すなら線形探索、何度も探すなら整列してから二分探索、というように使い分けます。

整列していないデータから 1 回だけ値を探すなら、線形探索と二分探索のどちらが向いているか？

線形探索

二分探索を使うには先に整列が要り、その手間のほうが線形探索 1 回より大きい。何度も探すなら整列して二分探索にする利点が出る。

線形探索で使う番兵とは何か？

探す値を配列の末尾に置いておき、必ず見つかるようにする工夫

「配列の終わりに来たか」を毎回調べなくてよくなり、1 回ごとの比較が減る。末尾の番兵で見つかったら「無い」と判断する。

番兵を置いた線形探索で、見つかった位置が番兵の位置だったら、何を意味するか？

もとのデータの中には、探す値が無かった

番兵は自分で置いた値なので、そこで見つかったのは「本当は無い」ということ。

練習問題

問 1　次のプログラムを実行すると、何と表示されるか。

data = [12, 5, 31, 8, 20, 17]
target = 20
count = 0
for i in range(len(data)):
    count = count + 1
    if data[i] == target:
        break
print(i, count)

4 5

線形探索。12, 5, 31, 8, 20 と 5 回比べ、添字 4 で見つかって break で抜ける。

問 2　次の二分探索で、mid はどんな値をとり、最後に何と表示されるか。

data = [3, 7, 11, 18, 24, 30, 36, 41, 57]
target = 36
lo = 0
hi = len(data) - 1
steps = 0
while lo <= hi:
    mid = (lo + hi) // 2
    steps = steps + 1
    if data[mid] == target:
        break
    elif data[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(mid, steps)

mid は 4、6 と変わり、「6 2」と表示される

1 回目: lo が 0、hi が 8 で mid は 4。data[4] の 24 は 36 より小さいので、lo を 5 にして後半に絞る。
2 回目: lo が 5、hi が 8 で mid は 6（13 を 2 で割った商）。data[6] が 36 で見つかる。9 個のデータから 2 回の比較で見つかった。

問 3　整列済みの 1000 個のデータから値を探す。線形探索と二分探索それぞれで、比較回数の最大は何回か。
二分探索は、問 2 のプログラムと同じ手順とする。

線形探索は 1000 回、二分探索は 10 回

二分探索は 1 回の比較で範囲がおよそ半分になる。1000 個が 500、250、125、62、31、15、7、3、1 個と絞られ、
最後の 1 個との比較まで含めて最大 10 回。2 を 10 回かけた 1024 が 1000 を超えることから見当がつく。