【高校情報１】探索アルゴリズム（線形探索と二分探索）Pythonプログラミング　動画解説

はじめに

第３章　コンピュータとプログラミング
学習１５　線形探索と二分探索　※ソートは次回解説予定

https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/1416756.htm

別動画でアップしているPython超入門講座は一通り理解している前提で進めています。

教員研修用教材に完全に準拠した形で解説しています。（P128～）

私が探索アルゴリズムをはじめて学んだのは、基本情報技術者試験を勉強し始めた時（大学生時）。
書籍読んでも訳が分からず、それがきっかけでバイトで貯めたお金をはたいて、１５万円もする大手資格の予備校のビデオ講座を頼んだ。
やはり動画だと分かりやすいと感じた時でした。

今回は、その内容よりさらにレベルアップした動画を作成してみました。

アニメーション作るの大変でしたが、これで探索アルゴリズムを理解してくれる人が増えたらいいなと思います。

一応文字おこしは書いていますが、動画見ないと、わけが分からないと思うので、動画中心に学習お願いします。

学校で教える先生も、毎回これを黒板で教えるの大変だろうな・・（この動画併用してほしいという想いもあります）

情報Ⅰ共通テスト対策 書籍出版します！

情報Ⅰ 大学入学共通テスト対策 会話型テキストと動画でよくわかる

◆◆解説動画◆◆

情報処理技術者試験・高校情報教科対策の突破口ドットコム

◆◆文字おこし◆◆

いままで、プログラミング演習でリストを扱ってきたけど、
リストなどの中から必要なデータを探し出すことを探索といい，線形探索や二分探索などがある

まず、線形探索について見ていこう
線形探索はリストを先頭から順に比較しながら探索値に一致する
データを探し出す探索方法

例えば
このようなリストaがあって、探したい値が82だったとする。
リストの先頭から数値を比較していく。
まずは６１と８２を比較して不一致だから次の比較に移る
１５と８２を比較して不一致だから次の比較に移る
そして次の比較で８２と一致するから、リスト添字２が該当箇所ということが分かる。

流れ図で表すとこんな感じになる。
実際の数値をいれて、流れを確認していこう。
まず探索値の入力で、８２を入れる
そして、添字を０から１ずつ増やしながら、データの数分繰り返す処理で何をやるかというと、さっきの説明と同じで
まずは６１と８２を比較して不一致だから次の比較に移る
１５と８２を比較して不一致だから次の比較に移る
そして次の比較で８２と一致するから　Yesの判定に入り一致場所を表示して処理を終了する。

Pythonプログラミングしていこう。

# 受渡されたリスト内の要素と比較値を比較し、一致した場合、添字を表示する。
# 関数名：linsearch
# 引数１：a（比較対象のリスト）引数２：p（探索値）
# 戻り値：なし　※関数内で結果を表示
def linsearch(a, p):
   for i in range(0, len(a), 1):
       if a[i] == p:
           print("見つかりました。添字 :", i)
           break

a = [61, 15, 82, 77, 21, 32, 53]
p = 82
linsearch(a, p)

比較対象のリストと探索値を引数として受け渡す関数を作成しよう。
一致するものが見つかった場合に、「見つかりましたと添字を表示するようにする」

まずは、def linserchと関数名を記載し丸カッコの中に引数の比較対象リストaと探索値pをカンマ区切りで入れて　コロンでとじます
そして、関数処理を記述する為、次の行をインデントして、
リストの要素数分比較を行うので、for文を記述します
for 変数のi 　rangeの中は　初期値０　len(a)でリストの要素数　増分は１
そしてその次の行をインデントして、添字iの要素と探索値pを比較します。
一致する場合の処理を記述するため、次の行をインデントして
print文の中に　見つかりました。と記述し、　そして該当箇所の添字を表示するためにカンマで区切って、変数iを記述する。
そして、一致した場合は、これ以上比較する必要ないので、break文でループの処理を終了する。

じゃあ、今度は関数の呼び出し部分を作っていこう。
まずは、引数として受け渡す、リストaと探索値の変数pを定義する　探索値は82とするね。
そしてlinsearchの関数の引数に今定義したリストaと変数pを記述する。
じゃあ、実行してみよう。
ちゃんと　見つかりました。添字２と表示されたね。

＝＝＝
今度は二分探索（にぶんたんさく）について説明していくね。
二分探索はリストの中から探索範囲を半分ずつ狭めながら目的のデータを探し出す探索方法なんだ。

１～９まで昇順に並び替えられたリストの例で説明するね。
二分探索を行う上で前提となるのは、並び替えていることなんだ。並び替えアルゴリズムは別途説明するね。

探索値は３とするね。
まずは、この１～９までのリストの中で真ん中位置するのは
５だよね。添字で表すと、一番左側の添字０と一番右側の添字８　を足して２で割った添字４の場所が該当する。

まず、その添字４の要素である５と探索値の３を比較する。探索値の方が小さいから、添字４より左側に探索値があることが分かり、探索範囲が狭まる。
今度その狭めた範囲、添字０から３の間での中央を求める。
さっきの計算式で言うと、０＋３をして÷２をすると、１．５と中途半端な数になるよね。
その場合は、小数点以下を切り捨てて、添字１である、２を中央値として、比較対象とする。
探索値の３と比較して、探索値の方が大きいから、次の比較対象は添字２から３の範囲となる。そして、次の中央値は添字２の３となり探索値と一致するから、添字２の場所が探索値がある場所となる。

これを流れ図で表すと、こんな感じになる。
実際に数値を当てはめながら処理を追っていこう。
比較対象のリストはaとして、探索値は４３とするね。

まず、探索値の入力は４３が対象となる。
そして、探索対象のリスト名はaとして定義する。

下限の添字は０
上限の添字はデータ数―１だから、今回はデータ数７から１マイナスして６となる。

下限の添字＜＝上限の添字　となるまで、処理を繰り返す。

そして、探索値と比較する中央値を求める為、（上限の添字＋下限の添字）÷２をする。小数点以下があった場合は切り捨てる。
今回は　下限０　上限は６が入っているから、中央の添字は６÷２で３となる。
添字３には５１が入っているからその５１と探索値の４３を比較すると、探索値の方が小さいから、中央の添字より左側に探索したいデータがあることが分かる。
範囲を狭めるために上限の添字に今の中央の添字―１をして、それを上限の添字に入れてあげる。
中央の添字は今は３だから１マイナスして２となる。
ループの初めに戻って、下限の添字０と上限の添字２をプラスして２で割ると、中央の添字は１となる。添字１の要素３３と探索値の４３を比較して探索値の方が大きいから、中央より右側に探索値があることが分かる。

条件分岐のＮＯの条件に入るから　今の中央の添字１に１をプラスした２を下限の添字に入れてあげる

ループのはじめにもどって、下限の添字は２、上限の添字は２だから　（２＋２）をして　÷２をすると中央の添字は２となる。

添字２の要素は４３で探索値と一致するから、一致場所を表示し処理を終了する。

# 二分探索で受渡されたリスト内の要素と探索値を比較する。
# 関数名：binsearch
# 引数１：a（比較対象のリスト）引数２：p（探索値）
# 戻り値：なし　※関数内で結果を表示
def binsearch(a, p):
   i = 0  # 下限添字
   j = len(a) - 1  # 上限添字
   while i <= j:
       m = int((i+j)/2)  # 中央添字（小数点以下切り捨て）
       if a[m] == p:
           print("見つかりました。添え字:", m)
           break
       else:
           if a[m] > p:
               j = m - 1
           else:
               i = m + 1

a = [25, 33, 43, 51, 66, 71, 88]
p = 43  # 探索値
binsearch(a, p)

じゃあ、今度はPythonでプログラミングしていこう

二分探索で受渡されたリスト内の要素と探索値を比較する
関数を作成する。
関数名は、binsearch 第一引数は 比較対象リストをa　第二引数は探索値をpとする
戻り値は関数内で結果を表示するのでなし

まずは、def binsearch　丸カッコの中に引数のaとｐを定義する
インデントをして　下限添字の変数iに初期値の０を代入する
そして　上限添字のjに、リストの要素数から１マイナスしたものを初期値として代入する。マイナス１しているのは添字は０からカウントするためだったよね。

次にwhile文を記述し、ループ継続条件は　下限添字が上限添字以下であることとする。
インデントをして
中央添字を求める　上限添字プラス下限添字の値を２で割る。小数点以下は切り捨てするために、int型にキャストしてあげる。それを変数mに代入する。

そして　if文を記述し　中央値と検索値が一致する場合は、　見つかりましたの文言と共に添字を出力し、break文でループの処理を抜けて処理を終了する。

探索値と一致しない場合は、else文に入って
中央値が探索値より大きい場合は、中央より左側に探索値があるということだから、
上限添字を変更する。中央添字からマイナス１した値を上限添字として変数jに代入する。

中央値が探索値より小さい場合は、中央より右側に探索値があるということだから
下限添字を変更する。中央添字から＋１した値を下限添字として変数iに代入する。
じゃあ、関数の呼び出しをしていこう。
まずは、リストを定義し変数aに代入する。
探索値は43として変数pに代入する。
binsearchの関数にaとpの引数を受け渡す。
実行してみよう。
ちゃんと　見つかりました。添え字２と表示されたね。

次に、線形探索と二分探索の最大比較回数を確認していこう。

線形探索はリスト内１つ１つと突き合わせするから、一番最後に一致する値が存在した場合はリストの要素数分突き合わせることになる。
なので、最大探索回数はリストの要素数と一致する。

二分探索は範囲を半分に狭めていくから、
最大探索回数はlog2 n＋１　回となる。

探索アルゴリズムはいきなりプログラムで見るとわかりずらいと思うけど、
どういう流れで探索していくかという論理をしっかり押さえておこう。

情報処理技術者試験・高校情報教科対策の突破口ドットコム