コンピュータ演習II 第12回 探索アルゴリズム

今回の主役は、リストの中から目当ての値を見つけ出す 探索（サーチ） です。第11回の整列（ソート）に続く、アルゴリズムの定番題材です。次の3 つを学びます。

1. 線形探索（先頭から順に調べる、いちばん素朴な探索）
2. 二分探索（整列済みのリストを、半分ずつに絞り込む探索）
3. アルゴリズムの良し悪し（比較回数を数えて2 つの探索を比べる。第11回の続き）

新しい文法は1 つも出てきません。これまでに学んだ for 文/if 文（if-elif-else）/論理演算子（and）だけで、代表的な探索アルゴリズムが書けます。

1. 探索とは

探索（サーチ） とは、データの集まりの中から、目当ての値を見つけ出す処理です。連絡先から友だちの名前を探す、商品一覧から目当ての商品を探す、辞書で単語を引く——どれも探索です。プログラムの世界でも、探索は整列と並ぶもっとも基本的なアルゴリズムです。

この資料では「リスト numbers の中に、探す値 target があるか。あるなら どの位置（添字） にあるか」という問題を考えます。

1.1 復習: アルゴリズムの読み方

第11回で学んだ読み方を、今回もそのまま使います。

• 手順/フローチャート/Python コードは、同じアルゴリズムの3 つの表現。
• 「はじめの値/進め方/続ける条件」の 3 点セット を見つけたら、まとめて1 つの for 文に畳む。
• 戻り以外の「〜ならば」は if 文になる。

今回はこれに、探索ならではの読み方が1 つ加わります。探索は 見つかったらそこでやめたい 処理です。ところが for 文は、途中でやめずに最後まで回り続けます。そこで「見つかったかどうかを変数で覚えておき、見つかった後は何もしない」という書き方を使います（2〜4 章で繰り返し出てきます）。

2. 線形探索

2.1 あるかないか

いちばん素朴な探索から始めます。先頭から順に1 つずつ、target と等しいかを調べる方法です。これを 線形探索 と呼びます。まず「あるかないか」だけを調べます。手順で書くと次のとおりです。

1. リスト numbers と探す値 target を用意する。見つかったかどうかを表す flg を 0 とし、位置 j を 0 とする。
2. numbers[j] が target と等しいならば、flg を 1 とする。
3. j を1 増やす。j がリストの長さより小さければ、手順2 へ戻る。
4. flg を出力する。

3 点セット（手順1 & 3）が1 組なので for 文1 つ、「〜ならば」（手順2）が1 か所なので if 文1 つでできる、と見当が付きます。 なお、flg はフラグ、旗です。 「見つかったかどうか」を表す変数で、0 なら「見つからなかった」、1 なら「見つかった」という意味です。 フラグが立つ、なんていう表現を聞いたことがあるかもしれませんが、まさにこのことです。

numbers = [4, 2, 7, 5, 7]
target = 5                        # 探す値

flg = 0                           # 見つかったら 1 にする(まだ見つかっていないので 0)
for j in range(0, len(numbers)):  # 先頭から末尾まで順に調べる
    if numbers[j] == target:      # target と等しければ
        flg = 1                   # 「見つかった」と記録する

print("見つかったか:", flg)

実行結果

見つかったか: 1

5 は3 番目にあるので、flg は途中で 1 になります。target = 3 に変えて実行すると、リストに 3 は無いので 0 のままです。いろいろな値で試してください。

2.2 どこにあるか（位置の探索）

「あるかないか」だけでなく、どの位置にあるか を知りたいことのほうが多いです（第11回の選択ソートでも、最小値の「位置」min_index を使いました）。見つかった位置を入れる変数 pos を用意し、見つけたら pos = j と記録します。

pos のはじめの値は -1 にします。0 だと「0 番目で見つかった」と区別が付きませんが、-1 は位置として存在しないので、「最後まで見つからなかった」の合図として使えます（探索の定番の書き方です）。

numbers = [4, 2, 7, 5, 7]         # 7 が2 か所にある
target = 7

pos = -1                          # 見つかった位置。-1 は「見つかっていない」の合図
for j in range(0, len(numbers)):
    if numbers[j] == target:
        pos = j                   # 見つかった位置を記録する

print("位置:", pos)

実行結果

位置: 4

7 は2 番目と4 番目の2 か所にあります。出力は 4、つまり 最後に見つかった位置 です。ループが最後まで回るので、pos は見つかるたびに上書きされ、後の位置が残るからです。

ふつう「探す」と言ったら、最初に見つかった位置 がほしいはずです。「すでに見つかっていたら（pos が -1 でなかったら）、もう上書きしない」という条件を、第04回で学んだ論理演算子 and で付け足します。

numbers = [4, 2, 7, 5, 7]
target = 7

pos = -1
for j in range(0, len(numbers)):
    if pos == -1 and numbers[j] == target:   # まだ見つかっていない、かつ等しい
        pos = j

print("位置:", pos)

実行結果

位置: 2

こんどは最初の 7 の位置（2）が出ました。pos == -1 and ... のように、「まだ見つかっていない」を条件に足して、見つかった後は何もしない——これが1 章でふれた、探索ならではの書き方です。下の図は、この流れをフローチャートで表したものです。

おまけ: break 文を使う

• break 文を使うと「見つかったらそこでfor 文を抜ける」という操作ができます。
• break 文は for 文を途中で抜ける命令です。
• break 文を使うと、pos の初期値を -1 にする必要はなく、pos を見つかった位置で上書きするだけで済みます。
• break 文を使うと、最初に見つかった位置を返すだけでなく、比較回数を減らすことができます。

例）

for i in range(len(numbers)):
    if numbers[i] == target:    # 見つかったら
        pos = i                 # 位置を記録
        break                   # for 文を抜ける

興味のある方は、break 文を使った線形探索のコードを書いてみると良いでしょう。

2.3 アルゴリズムとして読む

いま書いた線形探索（最初の位置）を、手順の形にまとめておきます。

1. リスト numbers と探す値 target を用意する。見つかった位置 pos を -1 とし、位置 j を 0 とする。
2. pos が -1 で、numbers[j] が target と等しいならば、pos を j とする。
3. j を1 増やす。j がリストの長さより小さければ、手順2 へ戻る。
4. pos を出力する。

第11回の規則で読むと、下のように対応します。

手順	見つかる言葉	コードでの形
1	（変数の用意）	numbers = ... と target = ... と pos = -1
1 & 3	j を 0 とし、1 増やして「手順2 へ戻る」	for j in range(0, len(numbers)):
2	「〜で、〜ならば」	if pos == -1 and numbers[j] == target: と pos = j
4	出力する	print(pos)

手順2 の「pos が -1 で、〜ならば」のように、条件が2 つ重なった「ならば」は、and で1 つの if 文 になります。この読み方も覚えておいてください。

3. 探索の手間: 比較回数

3.1 見つかった後は比べない

第11回と同じように、比較回数 を数えて探索の手間を測ります。ここで、2.2 の and の条件を 2 つの if 文に分けて 書き直します。意味は同じですが、分けると「外側の if と内側の if のあいだ」に、数える1 行を差し込めるようになります。

numbers = [4, 2, 7, 5, 7]
target = 7

pos = -1
compare_count = 0                         # target と比べた回数
for j in range(0, len(numbers)):
    if pos == -1:                         # まだ見つかっていないときだけ
        compare_count = compare_count + 1     # 比べる直前に数える
        if numbers[j] == target:          # target と比べる
            pos = j

print("位置:", pos)
print("比較回数:", compare_count)

実行結果

位置: 2
比較回数: 3

外側の if pos == -1: は、見つかった後の周回をまるごと飛ばす門番 の働きをしています（この資料では ガード と呼びます）。7 は2 番目で見つかるので、比べたのは 0・1・2 番目の3 回だけ。3 番目以降はガードに止められて、もう比べていません。下の図で、ガードの false の線が本体を飛ばして次の周回へ進む流れを確かめてください。

target をいろいろ変えて実行してください。

• target = 4（先頭にある）→ 比較は 1 回
• target = 5（後ろの方にある）→ 比較は 4 回
• target = 3（無い）→ 比較は 5 回（最後まで調べないと「無い」とは言い切れません）

target の場所によって手間が変わる、というのが線形探索の特徴です。リストが n 個なら、運が良ければ 1 回、最悪 n 回。リストが 1000 個・100万 個と大きくなると、この「最悪 n 回」が重くのしかかってきます。

4. 二分探索

4.1 基本的な考え方

紙の辞書で「探索」という単語を引くことを考えてみましょう。 このとき先頭の「あ」から1 ページずつめくる人はいません。 真ん中あたりを開いて、目当てより前か後ろかを見て、探す範囲を半分に絞る はずです。 これをそのままアルゴリズムにしたのが 二分探索 です。

二分探索には、大事な前提が1 つあります。リストが昇順に整列済みであること です。 整列されているからこそ、真ん中の値と比べるだけで「target は左半分にはない」などと、見てもいない半分をまとめて捨てられる のです。 辞書の例も同じです。 辞書は整列されているからこそ、真ん中のページを開いて「目当ての単語は前か後ろか」を判断できるのです。 第11回で学んだ整列は、この二分探索の下ごしらえでもあります。

この章ではまず、「半分に絞りながら探す」という動きを 探索木 という概念を使って、目で理解してから（4.2〜4.3）、それを Python のコードに落とします（4.4 以降）。

4.2 データを木にする（探索木）

整列済みのリスト numbers = [1, 2, 4, 5, 7, 8, 9] を例に、「真ん中と比べて半分に絞る」ときに 調べる可能性のある場所 を、全部描き出してみます。

1. 最初に調べるのは、必ず 全体の真ん中（位置 3 の 5）です。これをいちばん上に置きます。
   [1, 2, 4, 5, 7, 8, 9]
2. 5 より小さい側に絞ったら、次に調べるのは 左半分 [1, 2, 4] の真ん中（位置 1 の 2）です。
   [1, 2, 4]
   大きい側に絞ったら 右半分 [7, 8, 9] の真ん中（位置 5 の 8）です。
   [7, 8, 9]
   この2 つを、5 から枝を伸ばして左下と右下に置きます。
3. さらに「半分の半分」…と繰り返すと、最後は1 個だけの範囲（位置 0・2・4・6）が並んで終わります。

できあがった図は、枝分かれする形から 木 と呼ばれます。上下逆さの木に見立てて、いちばん上を 根、いちばん下を 葉 と呼びます。特にこの図は、二分探索が調べる場所を全部並べたものなので、この資料では 探索木 と呼びます。リストの7 個の要素が、どれも丸として1 回ずつ現れていることを確かめてください。整列済みのリストは、いつでもこの形の木に見立てられます。

なお、この木はプログラムのデータとして作るものではありません。頭の中（紙の上）でリストをこう見立てる、という 考え方の図 です。プログラムでどう表すかは、4.4 で説明します。

4.3 木の読み解き方

探索木ができてしまえば、探す手順は「根から下へたどる」だけです。ルールは3 つです。

• いま立っている丸の値と target を比べる。等しければ発見（その丸の位置が答え）。
• target のほうが 小さければ左の枝 へ、大きければ右の枝 へ下りる。
• 下りたい方向に 枝が無ければ（葉まで来てしまったら）、リストに 無い と分かる。

たとえば 7 を探すと、根の 5 と比べて（7 のほうが大きいので右へ）、次の 8 と比べて（小さいので左へ）、いちばん下の 7 と比べて発見。比較3 回 です。この道すじが、下の図のオレンジ色です。

無い値でも試します。3 を探すと、5（小さいので左へ）→ 2（大きいので右へ）→ 4（小さいので左へ…枝が無い）。比較3 回 で「無い」と言い切れます。指で図をたどって確かめてください。

この木から、二分探索の性質が3 つ読み取れます。

• どんな target を探しても、たどる道すじは 根から下への1 本道 です。
• 比較回数は「たどった段の数」なので、多くても木の段数（高さ）まで しかかかりません。7 個のリストなら3 段です。
• 1 段下りるごとに丸の数は2 倍に増えます。裏返すと、リストが倍の 15 個になっても 段は1 つ増えるだけ です。「1 回比べるごとに範囲が半分になる」を、この木の形として覚えておいてください。

4.4 木の探索経路を low と high で実装する

それでは、「木を根からたどる」を Python にします。木の図をデータとして作る必要はありません。木のどの丸も「そのとき残っている範囲の、真ん中」だったことを思い出してください。つまり、残っている範囲さえ覚えておけば、いま立っている丸の位置は計算で出せます。範囲は 左端 low と 右端 high の2 つの変数で表します。最初は low = 0、high = n - 1 でリスト全体の範囲を表します。いま立っている丸の位置は mid = (low + high) // 2 です（// は第02回の整数除算です。小数を切り捨てます）。

木の探索経路とコードは、次のように対応します。

木の探索経路（4.3 のルール）	コードでの形
根から始める	low = 0 と high = n - 1（範囲はリスト全体） [1low, 2, 4, 5, 7, 8, 9high]
いま立っている丸	mid = (low + high) // 2（範囲の真ん中） [1low, 2, 4, 5mid, 7, 8, 9high]
等しい → 発見	pos = mid
小さい → 左の枝へ	high = mid - 1（範囲を左半分に絞る） [1low, 2, 4high, 5, 7, 8, 9]
大きい → 右の枝へ	low = mid + 1（範囲を右半分に絞る） [1, 2, 4, 5, 7low, 8, 9high]
枝が無い → 「無い」	low が high を超える（範囲が空になる）

これをふまえて、二分探索をアルゴリズム（手順）として書きます。今回いちばん中身のある手順です。じっくり読んでください。

1. 昇順に整列されたリスト numbers を用意し、その長さを n とする。探す値 target を用意する。low を 0、high を n - 1、pos を -1、k を 0 とする。
2. low が high 以下ならば、手順3 へ進む。そうでないならば、手順7 へ進む。
3. mid を (low + high) // 2 とする。
4. numbers[mid] が target と等しいならば、pos を mid、low を high + 1 として、手順7 へ進む。そうでないならば、手順5 へ進む。
5. numbers[mid] が target より小さいならば、low を mid + 1 として、手順7 へ進む。そうでないならば、手順6 へ進む。
6. high を mid - 1 とする。
7. k を1 増やす。k が n より小さければ、手順2 へ戻る。
8. pos を出力する。

手順の書き方が1 つ増えています。「手順◯へ進む」は、あいだの手順を飛ばして先へ行く合図です（「戻る」が繰り返しの合図だったのに対し、「進む」は枝分かれの合図です）。手順4〜6 のように「〜ならば、…して手順7 へ進む。そうでないならば、次の手順へ進む」が連なっているところは、上から順に条件を調べて、最初に成り立った1 つだけを行う、つまり if-elif-else（第03回）そのものです。

第11回の規則と合わせて読みます。

手順	見つかる言葉	コードでの形
1 & 7	k を 0 とし、1 増やして「手順2 へ戻る」	for k in range(0, n):
2	「以下ならば手順3 へ/そうでないならば手順7 へ」	ガードの if low <= high:（3 章と同じ門番）
4〜6	「〜ならば、…して手順7 へ進む」の連なり	if / elif / else（第03回）

ポイントは2 つあります。

• for k in range(0, n): は「安全な上限」。木をたどるのは多くても段数まで（7 個なら3 段）ですが、n 回回しておけば確実に足ります。早く終わったあとの残りの周回は、ガード（low <= high が false）が全部飛ばします。3 章の「見つかった後は比べない」と同じ仕掛けです。
• 見つかったら low = high + 1 とする。範囲をわざと空にすることで、以降の周回では何も起きなくなります（「探索を終える」の合図です）。

numbers = [1, 2, 4, 5, 7, 8, 9]   # 昇順に整列済みであること!
target = 7
n = len(numbers)

low = 0                           # 探す範囲の左端
high = n - 1                      # 探す範囲の右端
pos = -1
for k in range(0, n):             # 多くても n 回で必ず終わる(安全な上限)
    if low <= high:               # ガード: 範囲が残っているときだけ
        mid = (low + high) // 2   # 真ん中の位置
        if numbers[mid] == target:
            pos = mid             # 見つかった
            low = high + 1        # 範囲を空にして探索を終える
        elif numbers[mid] < target:
            low = mid + 1         # 真ん中から左を捨てる
        else:
            high = mid - 1        # 真ん中から右を捨てる

print("位置:", pos)

実行結果

位置: 4

7 の位置（4）が出ました。4.3 で木をたどったとおりの答えです。下の図は、この流れをフローチャートで表したものです。ひし形が4 つ（ループ/ガード/等しいか/小さいか）並ぶ、今回いちばん大きな図です。「等しいか」の false が「小さいか」へ流れ落ちる形が、コードの if-elif-else に対応します。

4.5 動きを観察する

本当に「木の道すじのとおり」に絞れているのかを、目で確かめます。ガードの中に、調べる位置と範囲を出力する行を足します（第11回の「パスごとの出力」と同じ、観察用の行です）。

numbers = [1, 2, 4, 5, 7, 8, 9]
target = 7
n = len(numbers)

low = 0
high = n - 1
pos = -1
for k in range(0, n):
    if low <= high:
        mid = (low + high) // 2
        print("調べる位置:", mid, "/ 範囲:", low, "〜", high)   # 観察用
        if numbers[mid] == target:
            pos = mid
            low = high + 1
        elif numbers[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

print("位置:", pos)

実行結果

調べる位置: 3 / 範囲: 0 〜 6
調べる位置: 5 / 範囲: 4 〜 6
調べる位置: 4 / 範囲: 4 〜 4
位置: 4

1 回目は7 個全体（0〜6）の真ん中 3 を調べ、numbers[3]（5）は 7 より小さいので、範囲が右半分（4〜6）に絞られました。2 回目はその真ん中 5 を調べ、numbers[5]（8）は 7 より大きいので、範囲が左（4〜4）に絞られました。3 回目でその真ん中 4 を調べて、見つかりました。比較は 3 回（木の段数ぶん）で済んでいます。「調べる位置」の 3 → 5 → 4 は、4.3 の図のオレンジの道すじ（位置 3 の 5 → 位置 5 の 8 → 位置 4 の 7）そのものです。コードは木の図を持っていないのに、low と high だけで同じ道すじをたどれています。

target を 1 や 9（端の値）、3（無い値）に変えて、範囲の絞られ方を観察してください。

4.6 比較回数を数える

「多くても木の段数まで」を、実際に数えて確かめます。3 章と同じように数えます。ガードの中に compare_count = compare_count + 1 を置くだけです（範囲が残っていて、実際に比べた周回だけ数えます）。

numbers = [1, 2, 4, 5, 7, 8, 9]
target = 3                        # 無い値(いちばん手間のかかる場合)
n = len(numbers)

low = 0
high = n - 1
pos = -1
compare_count = 0
for k in range(0, n):
    if low <= high:
        mid = (low + high) // 2
        compare_count = compare_count + 1
        if numbers[mid] == target:
            pos = mid
            low = high + 1
        elif numbers[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

print("位置:", pos)
print("比較回数:", compare_count)

実行結果

位置: -1
比較回数: 3

無い値を探すのは、線形探索なら 7 回（全部）比べる最悪の場合ですが、二分探索は 3 回 で「無い」と言い切れます。1 回比べるごとに範囲がほぼ半分になるので、7 個 → 3 個 → 1 個 → 0 個と、3 回で範囲が尽きるからです。これは、4.3 で 3 を探して「無い」と分かった道すじ（5 → 2 → 4 の3 段）そのものです。

5. 大きなリストで比べる

7 個のリストでは「7 回と3 回」の差ですが、この差はリストが大きくなるほど劇的に開きます。1000 個のリストで確かめます。リストは第06回で学んだ append の蓄積で作ります（0, 2, 4, ... と2 ずつ増える、昇順の1000 個）。

# 0, 2, 4, ..., 1998 の1000 個の昇順リストを作る
numbers = []
for i in range(0, 1000):
    numbers.append(i * 2)

target = 1998                     # いちばん後ろの値(線形探索には最悪の場合)
n = len(numbers)

# --- 線形探索(3 章と同じ) ---
pos = -1
compare_count = 0
for j in range(0, n):
    if pos == -1:
        compare_count = compare_count + 1
        if numbers[j] == target:
            pos = j
print("線形探索: 位置", pos, "/ 比較", compare_count, "回")

# --- 二分探索(4 章と同じ) ---
low = 0
high = n - 1
pos = -1
compare_count = 0
for k in range(0, n):
    if low <= high:
        mid = (low + high) // 2
        compare_count = compare_count + 1
        if numbers[mid] == target:
            pos = mid
            low = high + 1
        elif numbers[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
print("二分探索: 位置", pos, "/ 比較", compare_count, "回")

実行結果

線形探索: 位置 999 / 比較 1000 回
二分探索: 位置 999 / 比較 10 回

同じ値を探して、線形探索は 1000 回、二分探索は 10 回 です。1 回ごとに範囲が半分になるので、1000 → 500 → 250 → ... → 1 と、10 回ほどで1 個まで絞れるからです（2 を10 回かけると 1024。4.2 の探索木で言えば、約10 段の木になります）。リストが 100万 個になっても、二分探索は 20 回ほどで済みます。

この「半分にできる回数」には、名前が付いています。2 を何回かけたら n になるか（= n を1 になるまで半分にできる回数）を、数学では log₂ n（ログ） と書きます。探索木の段数と同じものです。探す手間は いちばん運の悪い場合（最悪の場合） で見積もるのがふつうで、線形探索は n 回、二分探索は約 $\log_2 n$ 回、と言い表せます（n がちょうど2 のかけ算で作れる数でなくても、およその回数として使えます）。

リストの大きさ n	線形探索（最悪 = n 回）	二分探索（最悪 ≈ $\log_2 n$ 回）
7	7 回	3 回
1000	1000 回	10 回
100万	100万 回	20 回

第11回で学んだ「アルゴリズムの良し悪しは操作の回数で比べる」の、これが探索版です。回数を1 回きざみで正確に覚える必要はありません。大事なのは、n が大きくなったときに n に比例して増えるのか、$\log_2 n$ でしか増えないのか という 増え方の違い で、手間の見積もりはこのくらい大まかで十分です。同じ問題でも、アルゴリズムしだいで手間が桁違いに変わります。ただし二分探索が使えるのは 整列済みのリストだけ です。整列されていないリストには線形探索、整列済みのリストには二分探索、という使い分けになります。

6. 整列してから探す

バラバラのリストで二分探索を使いたいときは、先に整列してから探し ます。第11回のバブルソートと、今回の二分探索をつなげるだけです。

numbers = [8, 3, 6, 1, 9]         # バラバラのリスト
target = 8
n = len(numbers)

# --- まず整列する(第11回のバブルソート・昇順) ---
for i in range(0, n - 1):
    for j in range(0, n - 1 - i):
        if numbers[j] > numbers[j + 1]:
            tmp = numbers[j]
            numbers[j] = numbers[j + 1]
            numbers[j + 1] = tmp
print("整列後:", numbers)

# --- 整列済みになったので、二分探索で探す ---
low = 0
high = n - 1
pos = -1
for k in range(0, n):
    if low <= high:
        mid = (low + high) // 2
        if numbers[mid] == target:
            pos = mid
            low = high + 1
        elif numbers[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
print("target の位置:", pos)

実行結果

整列後: [1, 3, 6, 8, 9]
target の位置: 3

1 つ注意があります。出力の 3 は 整列後のリストでの位置 です。8 は元のリストでは 0 番目にありましたが、整列で要素の位置が変わりました。元のリストでの位置が知りたい問題では、整列せずに線形探索を使います。「元の位置がほしいなら線形探索、速く探したいなら整列して二分探索」——目的に合わせて使い分けてください。

「整列（第11回）と探索（今回）はセットで使われる」——2 回分の内容がここでつながりました。

7. フローチャートで流れをつかむ

この資料の図は、これまでどおり 流れを目で確かめるためのヒント です。読み方のポイントは次の2 つです。

• ガードのひし形: 3 章と4 章の図では、ループの中にガード（pos == -1 や low <= high）のひし形があり、false の線が本体を丸ごと飛ばして次の周回へ進みます。「見つかった後は何もしない」が、図では「本体を通らない線」として見えます。
• 二分探索のひし形は4 つ: ループ/ガード/等しいか/小さいか。「等しいか」の false が「小さいか」へ流れ落ちる形が、コードの if-elif-else に対応します。フローチャートが「1 周の処理の流れ」を表すのに対し、4.2〜4.3 の探索木は「周をまたいだ調べる順」を表します。同じ二分探索の、別の面を見る図です。

そして今回は、課題について 大きな変更 が1 つあります。授業後の課題は、Python ではなく、フローチャートツールでフローチャートを組んで提出 します（全問）。使うのはこの授業のための フローチャートツール（ https://moss-yk.com/tools/flowchart/ ）です。ブラウザで開いてノードを並べ、線でつなぎ、その場で実行して出力を確かめられます。第11回の課題の発展問題で使ったものと同じツールです（発展問題をやらなかった人も、課題ページに使い方を書いてあるので大丈夫です）。

フローチャートで組むということは、手順の構造（ループ・分岐・ガード）がそのまま提出物になる ということです。この資料の図とコードを見比べて、対応を頭に入れておいてください。

まとめ

• 探索 は、リストの中から目当ての値（target）を見つけ出す処理。見つかった位置は pos に入れ、-1 を「見つからなかった」の合図 にする。
• 線形探索 は先頭から順に1 つずつ比べる。整列されていないリストにも使える。比較回数は、運が良ければ 1 回、最悪 n 回。
• for 文は途中でやめられないので、ガード（if pos == -1: などの門番の if）で「見つかった後は何もしない」を作る。比較回数はガードの中で数える。
• 二分探索 は 昇順に整列済み のリスト専用。範囲を low・high で持ち、真ん中 mid = (low + high) // 2 と比べて範囲を半分に絞る。見つかったら low = high + 1 で範囲を空にして終える。ループは for k in range(0, n): の「安全な上限」で回す。
• 二分探索が調べる位置の分かれ道を全部描いたものが 探索木。たどるのは根から下への1 本道で、比較回数は多くても木の段数（高さ）まで。この回数は「半分にできる回数」= log₂ n（探索木の段数）で、1000 個なら約 10 回、100万 個でも約 20 回。手間は最悪の場合で大まかに見積もれば十分。整列済みなら桁違いに速い。バラバラのリストは 整列してから探す（第11回とのつながり）。
• 授業後の課題は、フローチャートツール（ https://moss-yk.com/tools/flowchart/ ）でフローチャートを組んで .pflow を提出する（詳しくは課題ページ）。

今回いちばん身につけてほしいのは、「同じ問題でも、アルゴリズムしだいで手間が桁違いに変わる」 という感覚と、手順を読んで構造（ループ・ガード・分岐）に翻訳する力です。