アルゴリズム入門（探索）⌗

レッスン104で学んだようにある課題に対してそれを解決するための処理手順のことを「アルゴリズム」といいます。

今回は探索のアルゴリズムをフローチャートを使って学び、フローチャートに基づいてプログラムを作成してみましょう。

探索あるいは検索とは、データの集合の中から目的の要素を探し出す処理です。

線形探索⌗

線形探索は、配列の先頭から各要素が目的の値と等しいかどうを順番に調べます。等しいものが見つかった時点でその位置を返し探索を終了します。末尾まで調べて目的の値が存在しなかった場合はそのことを示す特別な値（たとえば-1）を返します。アルゴリズムの効率は悪いですが、線形探索はデータの並びに関係なく適用することができます。

例題⌗

n個の整数を含む数列（配列）Sと、q個の異なる整数を含む数列（配列）Tを読み込み、Tに含まれる整数の中でSに含まれるものの個数Cを出力するプログラムを作成しなさい。

入力

１行目にn、2行目にSを表すn個の整数（空白区切り）、3行目にq、4行目にＴを表すq個の整数が与えられます。
出力

Cを1行に出力してください。

フローチャート⌗

%%{init:{'themeVariables':{'lineColor':'#FFFFFFFF'}}}%% flowchart TD A("search(S, n, key)") --> B[i = 0] --> C{i < n} -- Yes --> D{"S[i] == key"} -- Yes --> E(return True) D -- No --> F[i += 1] --> C C -- No ---> G(return False)

%%{init:{'themeVariables':{'lineColor':'#FFFFFFFF'}}}%% flowchart TD A(開始) --> B[/nを読み込む/] --> C[i = 0] --> D{i < n} -- Yes --> E["S[i]を読み込む"] --> F[i += 1] --> D D --- No ---> G[/qを読み込む/] --> H[Sum = 0] --> I[i = 0] --> J{i < q} -- Yes --> K["keyを読み込む"] --> L[["search(S, n, key)"]] --> M{結果がTrue} -- Yes --> N[Sum += 1] --> O[i += 1] --> J M -- No --> O J -- No -----> P[/Sumを書き出す/] --> Q(終了)

プログラムを作ってみよう（課題）⌗

上記フローチャートからPythonでプログラムを作ってみましょう。完成したら以下のテストデータを入力し、正しく出力されるか確かめてみましょう。

入力例

出力例

ヒント⌗

Pythonでデータを入力するにはinput()という関数を使用します。

input()では1行分のデータが文字列として取得されます。

従ってnやqのような1個の数値を取得する際はint()という関数で文字列を数値に変換し、n = int(input())のようにして取得します。

スペース（空白）で区切られたSのような数列（配列）を取得する際は、split(" ")という関数を使用して、" "（スペース（空白））で文字列を分割し、文字列の配列として取得します。（ary = input().split(" ")のようにaryという文字列配列を取得します）

その後配列の各要素をint()関数で数値に変換します。

変換した値を数値の配列Sに入れる際にはS = []のように空の配列に初期化し、後からs.append()という関数で値を追加していきます。

関数は

def 関数名(引数):
	処理内容
	return 戻り値

のように書きます。この関数を呼ぶには関数名（引数）のように書きます。

回答例

def search(S, n, key):
    for i in range(n):
        if key == S[i]:
            return True
    return False

n = int(input())
S = []
ary = input().split(" ")
for i in range(n):
    S.append(int(ary[i])
Sum = 0
q = int(input())
ary = input().split(" ")
for i in range(q):
    key = int(ary[i])
    if search(S, n, key):
        Sum += 1
print(Sum)

二分探索⌗

数列（配列）が昇順（または降順）にソートされて並んでいる場合、二分探索というアルゴリズムを使用してより高速な探索を行うことができます。

アルゴリズムは以下の通りです。

数列（配列）全体を探索の範囲とします。
探索の範囲内の中央の要素を調べます。
目的の値と中央の要素の値が一致すれば、探索を終了します。（探索成功）
目的の値が中央の要素の値よりも小さければ、探索範囲の前半部分を、大きければ探索範囲の後半部分を新たな探索範囲として2.の処理に戻ります。
その際、探索範囲がなくなれば（探索の右端と左端が一致すれば）、探索を終了します。（探索失敗）

具体的な例を見てみましょう。次の図は、昇順に整列された14個の要素を含む数列（配列）Sから、二分検索によりkeyの値36を探す様子です。

  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
[ 1   3   6   7  10  11  15  23  36  51  64  86 103 121 ]
left                          ↑ mid                     right
1回目                         36
                               [ 36  51  64  86 103 121 ]
　　　　　　　　　　　　　　　　　　　left 　　　　　 ↑ mid     right
2回目　　　　　　　　　　　　　　　　　　　　　　　　 36
                               [ 36  51  64 ]
                               left   ↑ mid right
3回目　　　　　　　　　　　　　　　　　　　 36
                               [ 36 ]
                             left ↑ mid right
4回目                             36

まず二分検索はデータ全体を探索範囲とするので、leftは0に、rightは要素数のn(=14)に初期化し、探索範囲を0以上n未満にします。
次に、現時点の探索範囲の中央の位置midを(left + right) / 2（整数に丸める）で求めます。 mid = (0 + 14) / 2 = 7になります。（1回目）
- keyの値36は中央の要素S[7]の値23より大きいので、次の探索範囲を現在の探索範囲の後半部分にします。すなわち、探索範囲の左端（left）の値を中央の位置(mid) + 1の8にして、探索範囲を8以上n未満にします。
次に、新しい探索範囲の中央の位置midを(left + right) / 2（整数に丸める）で求めます。 mid = (8 + 14) / 2 = 11になります。（2回目）
- keyの値36は中央の要素S[11]の値86より小さいので、次の探索範囲を現在の探索範囲の前半部分にします。すなわち、探索範囲の右端（right）の値を中央の位置(mid) の11にして、探索範囲を8以上11未満にします。
次に、現時点の探索範囲の中央の位置midを(left + right) / 2（整数に丸める）で求めます。 mid = (8 + 11) / 2 = 9になります。（3回目）
- keyの値36は中央の要素S[9]の値51より小さいので、次の探索範囲を現在の探索範囲の前半部分にします。すなわち、探索範囲の右端（right）の値を中央の位置(mid) の9にして、探索範囲を8以上9未満にします。
次に、現時点の探索範囲の中央の位置midを(left + right) / 2（整数に丸める）で求めます。 mid = (8 + 9) / 2 = 8になります。（4回目）
- keyの値36は中央の要素S[8]の値36と等しいので探索を終了し、見つかったのでTrueを返します。
なお、例えばkeyの値を37とすると、３回目までは上記と同様の処理になりますが、4回目の処理ではkeyの値37は中央の要素S[8]の値36より大きいので、索範囲の左端（left）の値を中央の位置(mid) + 1の9にします。この値は探索範囲の右端（right）の値9と等しくなり、右端と左端が一致して探索範囲がなくなったので、探索を終了し、見つからないFalseを返します。
同様に、例えばkeyの値を35とすると、３回目までは上記と同様の処理になりますが、4回目の処理ではkeyの値35は中央の要素S[8]の値36より小さいので、索範囲の右端（right）の値を中央の位置(mid) の8にします。この値は探索範囲の右端（left）の値8と等しくなり、右端と左端が一致して探索範囲がなくなったので、探索を終了し、見つからないFalseを返します。

処理速度については、例えばデータの数が100個の場合、線形探索では、最初の値が探索する値なら1回の探索で済みますが、最後尾まで見つからなければ最悪100回の探索が必要になります。一方、二分検索では、最悪でも8回探索すれば数値が見つかるあるいは見つからないことがわかります。

例題⌗

n個の整数を含む数列（配列）Sと、q個の異なる整数を含む数列（配列）Tを読み込み、Tに含まれる整数の中でSに含まれるものの個数Cを出力するプログラムを作成しなさい。ただし、数列（配列）Sは昇順にソートされているものとします。

入力

１行目にn、2行目にSを表すn個の整数（空白区切り）、3行目にq、4行目にＴを表すq個の整数が与えられます。
出力

Cを1行に出力してください。

フローチャート⌗

%%{init:{'themeVariables':{'lineColor':'#FFFFFFFF'}}}%% flowchart TD A("binarySearch(S, n, key)") --> B[left = 0] --> C[right = n] --> D{left < right} -- Yes --> E["mid = (left + right) / 2"] --> F{"key == S[mid]"} -- Yes ----> G(return True) F -- No --> H{"key > S[mid]"} -- Yes --> I[left = mid + 1] --> D H -- No --> J[right = mid] --> D D -- No ------> K(return False)

%%{init:{'themeVariables':{'lineColor':'#FFFFFFFF'}}}%% flowchart TD A(開始) --> B[/nを読み込む/] --> C[i = 0] --> D{i < n} -- Yes --> E["S[i]を読み込む"] --> F[i += 1] --> D D --- No ---> G[/qを読み込む/] --> H[Sum = 0] --> I[i = 0] --> J{i < q} -- Yes --> K["keyを読み込む"] --> L[["binarySearch(S, n, key)"]] --> M{結果がTrue} -- Yes --> N[Sum += 1] --> O[i += 1] --> J M -- No --> O J -- No -----> P[/Sumを書き出す/] --> Q(終了)

プログラムを作ってみよう（課題）⌗

入力例

出力例

ヒント⌗

データの入力の方法は線形探索のときと同様です。

回答例

def binarySearch(S, n, key):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if key == S[mid]:
            return True
        elif key > S[mid]:
            left = mid + 1
        else:
            right = mid
    return False

n = int(input())
S = []
ary = input().split(" ")
for i in range(n):
    S.append(int(ary[i])
Sum = 0
q = int(input())
ary = input().split(" ")
for i in range(q):
    key = int(ary[i])
    if binarySearch(S, n, key):
        Sum += 1
print(Sum)

レッスン106

アルゴリズム入門（探索）⌗

線形探索⌗

例題⌗

フローチャート⌗

プログラムを作ってみよう（課題）⌗

ヒント⌗

二分探索⌗

例題⌗

フローチャート⌗

プログラムを作ってみよう（課題）⌗

ヒント⌗