LESSON 10

二分探索で素早く探そう

並べ替えられたリストを半分ずつにしぼって探します。

40分
必須
必須・これまでの復習

これまでの内容から、3問を復習しよう

前回までの内容から、毎回ランダムに3問が選ばれます。同じ復習用ファイルの中身を書き換え、1問ずつ予想・実行します。

今回のファイル名lesson10_review.py

レッスン番号と使う場面が分かる名前にして、あとで探しやすくします。

  1. VS Code上部の「ファイル」をクリック
  2. 「新しいテキスト ファイル」をクリック
  3. Ctrl＋S（Macは⌘＋S）を押す
  4. lesson10_review.pyと入力して「保存」を押す

ここを確認：画面上のタブ、または左側のファイル一覧にlesson10_review.pyと表示されたら準備完了です。

復習 1・第1回

表示

print(3 + 4)

表示される数は？

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「表示される数は？」の答えとして何を確かめるのか決めます。
  2. 次にコードを上から読みます。変数へ入る値、繰返し、条件分岐が出てきたら、その行で何が変わるかを一つずつ紙に書きます。
  3. 最後に表示される値や残った値を選択肢と比べます。この問題では「3と4を足して7です。」という流れに注目します。
ヒントを見る

コードを自分で考えて作る問題ではありません。上にある見本コードを、復習用ファイルへ一文字ずつそのまま入力します。入力したら保存し、VS Code右上の▶を押します。画面下のターミナルに出た結果と選択肢を比べてください。記号や字下げが分からないときは、見本と同じ位置・同じ数にそろえれば大丈夫です。

復習 2・第2回

変数

x = 5
x = x + 2
print(x)

最後のxは？

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「最後のxは？」の答えとして何を確かめるのか決めます。
  2. 次にコードを上から読みます。変数へ入る値、繰返し、条件分岐が出てきたら、その行で何が変わるかを一つずつ紙に書きます。
  3. 最後に表示される値や残った値を選択肢と比べます。この問題では「5に2を足して7です。」という流れに注目します。
ヒントを見る

コードを自分で考えて作る問題ではありません。上にある見本コードを、復習用ファイルへ一文字ずつそのまま入力します。入力したら保存し、VS Code右上の▶を押します。画面下のターミナルに出た結果と選択肢を比べてください。記号や字下げが分からないときは、見本と同じ位置・同じ数にそろえれば大丈夫です。

復習 3・第3回

条件分岐

n = 8
if n > 5:
    print("大")

表示される文字は？

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「表示される文字は？」の答えとして何を確かめるのか決めます。
  2. 次にコードを上から読みます。変数へ入る値、繰返し、条件分岐が出てきたら、その行で何が変わるかを一つずつ紙に書きます。
  3. 最後に表示される値や残った値を選択肢と比べます。この問題では「8は5より大きいからです。」という流れに注目します。
ヒントを見る

コードを自分で考えて作る問題ではありません。上にある見本コードを、復習用ファイルへ一文字ずつそのまま入力します。入力したら保存し、VS Code右上の▶を押します。画面下のターミナルに出た結果と選択肢を比べてください。記号や字下げが分からないときは、見本と同じ位置・同じ数にそろえれば大丈夫です。

復習を終えたことを確認

実際に自分のパソコンで行ってから、チェックを入れてください。

◎
今日のゴール

二分探索の「真ん中を見る→半分を捨てる」を説明し、コードの変化を追える。

  • ✓並べ替えが必要な理由を言える
  • ✓left・right・midの場所を追える
  • ✓線形探索との違いが分かる
STEP 1

なぜ半分ずつ探すの？

今からやること
  1. 前回のwhileとbreakを思い出す
  2. 日常の例と図で二分探索を知る
  3. 短いリストで真ん中を調べる
  4. Pythonで二分探索を実行する
  5. 調べた場所を紙に書いて追う
  6. 必須問題で自分で確かめる

国語辞典で「りんご」を探すとき、最初のページから1ページずつ見ません。真ん中を開き、もっと前か後ろかを考えます。二分探索も同じです。

第8回：小さい順→真ん中を見る→候補を半分にする→第9回：条件まで繰返す

この講座では：3つの変数が「残った範囲の左・右・中央」を表すと読めれば十分です。

STEP 2

まず紙の上で探そう

小さい順のリストから8を探します。最初の真ん中は6です。8は6より大きいため、左半分はもう調べません。

調べない02
調べない14
真ん中26
次に見る38
候補410

6を見た次に調べる側は？

STEP 3

Pythonで二分探索を動かそう

今回のファイル名lesson10_step03.py

レッスン番号と使う場面が分かる名前にして、あとで探しやすくします。

  1. VS Code上部の「ファイル」をクリック
  2. 「新しいテキスト ファイル」をクリック
  3. Ctrl＋S（Macは⌘＋S）を押す
  4. lesson10_step03.pyと入力して「保存」を押す

ここを確認：画面上のタブ、または左側のファイル一覧にlesson10_step03.pyと表示されたら準備完了です。

この順番で実践します
  1. lesson10_step03.pyへ、見本コードを一文字ずつ入力する
  2. まだ実行せず、結果を予想する
  3. 保存して、VS Code右上の▶を押す
  4. 下のターミナルと教材の結果を比べる
A = [2, 4, 6, 8, 10]
target = 8
left = 0
right = len(A) - 1

while left <= right:
    mid = (left + right) // 2
    print("調べた値", A[mid])
    if A[mid] == target:
        print("見つけた")
        break
    elif A[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

『調べた値』はどの順に表示される？

先に自分のパソコンで実行しましょう。画面に出た結果を見てから、下のボタンを押します。

STEP 4

ここまで分かったか確認しよう

今回のファイル名lesson10_step04.py

この回の必須問題で使うファイルです。問題ごとに中身を書き換えます。

  1. VS Code上部の「ファイル」をクリック
  2. 「新しいテキスト ファイル」をクリック
  3. Ctrl＋S（Macは⌘＋S）を押す
  4. lesson10_step04.pyと入力して「保存」を押す

ここを確認：画面上のタブ、または左側のファイル一覧にlesson10_step04.pyと表示されたら準備完了です。

必須問題の進め方
  1. lesson10_step04.pyを作る
  2. 問題のコードを入力して保存・実行する
  3. 同じファイルを書き換えて次の問題へ進む
必須 1

4を探す

見本のtargetを4へ変え、調べる値の順番を確認します。

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「何を作るか」「最後に何を表示するか」を確認します。

  2. 見本全体を使い、変更するのはtargetの値だけです。表示された値を上から記録します。

  3. 次にコードを上から一行ずつ読みます。値が変わるたびに紙へ書き、最後の結果が問題の条件に合うか確かめます。
ヒントを見る

target = 4に直し、ほかは変えずに実行します。

答えを見る
A=[2,4,6,8,10]
target=4
left=0
right=len(A)-1
while left<=right:
    mid=(left+right)//2
    print("調べた値", A[mid])
    if A[mid]==target:
        print("見つけた")
        break
    elif A[mid]<target:
        left=mid+1
    else:
        right=mid-1
# 6、2、4、見つけた と表示されたら成功
必須 2

見つからない場合

targetを7にして、最後まで動かします。

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「何を作るか」「最後に何を表示するか」を確認します。

  2. 7と中央の値を比べ、leftまたはrightがどのように変わるか追います。

  3. 次にコードを上から一行ずつ読みます。値が変わるたびに紙へ書き、最後の結果が問題の条件に合うか確かめます。
ヒントを見る

必須1の完全なコードでtarget=7にします。見つけた、は表示されません。

答えを見る
A=[2,4,6,8,10]
target=7
left=0
right=len(A)-1
while left<=right:
    mid=(left+right)//2
    print("調べた値", A[mid])
    if A[mid]==target:
        print("見つけた")
        break
    elif A[mid]<target:
        left=mid+1
    else:
        right=mid-1
print("探索終了")
# 6、8、探索終了 と表示されたら成功
必須 3

線形探索と比べる

10を探すとき、先頭から探す場合と二分探索の回数を比べます。

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「何を作るか」「最後に何を表示するか」を確認します。

  2. 同じ10を探し、二つの方法でprintされた「確認」の行数を比べます。

  3. 次にコードを上から一行ずつ読みます。値が変わるたびに紙へ書き、最後の結果が問題の条件に合うか確かめます。
ヒントを見る

次の完全なコードを実行し、最後の2行の回数を比べます。

答えを見る
A=[2,4,6,8,10]
target=10
linear=0
for n in A:
    linear+=1
    if n==target:
        break
left=0
right=len(A)-1
binary=0
while left<=right:
    mid=(left+right)//2
    binary+=1
    if A[mid]==target:
        break
    elif A[mid]<target:
        left=mid+1
    else:
        right=mid-1
print("線形探索", linear)
print("二分探索", binary)
# 線形探索 5、二分探索 3 と表示されたら成功
実践したことを確認

実際に自分のパソコンで行ってから、チェックを入れてください。

共通テストとのつながり

共通テスト型の問題を3問解こう

Pythonで動かした経験を思い出し、コードを上から読みます。まず自分で考え、困ったときだけボタンを開きましょう。

問題 1

最初に調べる値

A = [2, 4, 6, 8, 10, 12, 14]
二分探索で12を探す

最初に調べる値は？

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「最初に調べる値は？」の答えとして何を求めるのか確認します。
  2. 値の上に場所の番号を書き、左右の中央を選びます。
  3. 最後にコードを上から追った結果を選択肢と比べます。「7個の真ん中は4番目の8です。」となる流れを確かめます。
ヒントを見る

最初と最後から同じ数だけ進んだ場所を見ます。

答えを見る

最初は中央の8を調べます。

問題 2

次に残す範囲

A = [2, 4, 6, 8, 10]
target = 4
最初に6を調べた

次に残す範囲は？

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「次に残す範囲は？」の答えとして何を求めるのか確認します。
  2. targetと真ん中の値を比べ、targetがある可能性のある側だけを残します。
  3. 最後にコードを上から追った結果を選択肢と比べます。「4は6より小さいため左半分を残します。」となる流れを確かめます。
ヒントを見る

4は6より小さいです。

答えを見る

左側の2、4を残します。

問題 3

調べた回数

A = [1, 3, 5, 7, 9]
二分探索で9を探す
調べた値：5 → 7 → 9

何回調べた？

考え方を見る

最初から全部を理解しなくて大丈夫です。問題を小さな処理に分け、上から順番に見ていきます。

  1. 最初に問題文を読み、「何回調べた？」の答えとして何を求めるのか確認します。
  2. 矢印で区切られた値を一つずつ数えます。
  3. 最後にコードを上から追った結果を選択肢と比べます。「5、7、9の三つを調べています。」となる流れを確かめます。
ヒントを見る

最初の5も1回に含みます。

答えを見る

3回です。

時間が余ったら

できるだけ解いてみよう

全10問

全部終わらなくても大丈夫です。上から順番に挑戦しましょう。

  1. 1. [1,3,5,7,9]から7を探す
    ヒントを見る

    最初の真ん中5と比べます。

    答えを見る
    調べる順番：5 → 7
  2. 2. [2,4,6,8,10]から2を探す
    ヒントを見る

    真ん中6より小さい側へ進みます。

    答えを見る
    調べる順番：6 → 2
  3. 3. 9がないことを確かめる
    ヒントを見る

    leftがrightを越えたら終了です。

    答えを見る
    [2,4,6,8,10]には9がない。
  4. 4. 並べ替えていないリストで使えない理由
    ヒントを見る

    半分を捨てる判断ができるか考えます。

    答えを見る
    左右の大小が決まっておらず、不要な半分を選べないため。
  5. 5. leftの役割を説明する
    ヒントを見る

    探す範囲の左端です。

    答えを見る
    leftは、まだ探す範囲のいちばん左の添字。
  6. 6. rightの役割を説明する
    ヒントを見る

    探す範囲の右端です。

    答えを見る
    rightは、まだ探す範囲のいちばん右の添字。
  7. 7. midの計算を書く
    ヒントを見る

    左右の添字を足して2で割ります。

    答えを見る
    mid = (left + right) // 2
  8. 8. targetが真ん中より大きい場合
    ヒントを見る

    左側を捨てます。

    答えを見る
    left = mid + 1
  9. 9. targetが真ん中より小さい場合
    ヒントを見る

    右側を捨てます。

    答えを見る
    right = mid - 1
  10. 10. 線形探索と二分探索を使い分ける
    ヒントを見る

    並べ替え済みかを確認します。

    答えを見る
    未整列なら線形探索、整列済みで高速に探すなら二分探索。