アルゴリズムとは、問題を解くための手順や方法のことです。
アルゴリズムは、プログラムを作成する際に非常に重要な要素であり、効率的なアルゴリズムを選択することで、プログラムの処理速度を向上させることができます。
この章では、アルゴリズムの基本である探索について学びます。
探索とは、データの中から目的のデータを見つけることです。
例えば、ある数値が配列の中に存在するかどうかを調べる場合、その数値が配列の中にあるかどうかを探索することになります。
線形探索は、データの先頭から順番に探索していく方法です。
データが整列されていない場合や、データの中に目的のデータが少ない場合に有効な探索方法です。
線形探索の実装として「数値が並ぶ配列list1の中に、目的の数値targetが存在するかどうかを調べる」プログラムを作成することを考えてみましょう。細かな要件は以下の通りです：
list1の中に目的の数値targetが存在する場合 →「(target)は配列の(n)番目の要素です」と出力する。list1の中に目的の数値targetが存在しない場合 →なにも出力しない。list1は、重複する数値を含まない。すなわち 配列list1内で同じ数値が複数回登場することはないものとする。実装の目標としては、配列list1の先頭から順に格納されている数字を見ていき、目的の数値targetと一致するものがあれば、そのインデックス（配列の何番目にあるか）を返せばよいでしょう。
配列の各要素にアクセスするためには、インデックスを指定してlist1[i]のように書くことで、配列list1のi番目の要素にアクセスすることができます。
また、「目的の数値targetと一致するか？」は、条件分岐を使って判定することができます。
例えば、配列の1番目が目的の数値16と一致する場合に「数値が一致した場合の処理」を行うには、if文や配列へのアクセスを用いて、以下のように書くことができます。
list1 = [16, 52, 31, 48, 9]
target = 16
if「ア」:
print(f"{target}は配列の1番目の要素です") # 数値が一致した場合の処理上記のプログラムの「ア」の部分にはどのようなコードを入れればよいでしょうか？
答え：list1[0] == target
list1 = [16, 52, 31, 48, 9]
target = 16
if list1[0] == target:
print(f"{target}は配列の1番目の要素です") # 数値が一致した場合の処理list1[0]は、配列list1の1番目の要素を表します。
if list1[0] == target:と書くことで、list1の1番目の要素がtargetと一致するかどうかを判定し、一致する場合にprint("数値が一致！")を実行します。なお、配列のインデックスは0から始まることに注意してください。配列の最初の要素はlist1[0]であり、2番目の要素はlist1[1]で参照します。
上記のプログラムの比較対象である配列の要素を、配列の先頭から順に見ていけば、目的の数値と一致するかどうかを判定することができます。そのため、以下のように配列の要素を順番に比較すれば、目的の数値が配列の中に存在するかどうかを調べることができます。
list1 = [16, 52, 31, 48, 9]
target = 16
if list1[0] == target:
print(f"{target}は配列の1番目の要素です")
if list1[1] == target:
print(f"{target}は配列の2番目の要素です")
if list1[2] == target:
print(f"{target}は配列の3番目の要素です")
if list1[3] == target:
print(f"{target}は配列の4番目の要素です")
if list1[4] == target:
print(f"{target}は配列の5番目の要素です")しかし、上記のプログラムでは、配列の要素を1つずつ比較するため、配列の要素数が多い場合には非常に冗長なプログラムになってしまいます。配列の長さが100個や1000個になった場合、同じように100個や1000個のif文を書く必要があります。
そこで、配列の要素数が多い場合でも対応できるように、繰り返し処理を使ってプログラムを簡潔にする方法を考えてみましょう。今回は、for文を使って配列の要素を順番に見ていき、目的の数値と一致するかどうかを判定する方法を考えてみましょう。色々な書き方がありますが、今回は以下のような実装にしてみましょう。
list1の長さを取得するlist1の長さだけ繰り返し処理を行うlist1のi番目の要素と目的の数値targetを比較するなお、配列の長さの取得には、len(配列)という関数を使うことができます。これは引数で渡した配列の長さ（数値）を返す組み込み関数です。
list1 = [16, 52, 31, 48, 9]
target = 31
length = len(list1) # len(配列)：配列の長さを取得する組み込み関数
for i in 「ア」:
if list1[i] == target:
print(f"{target}は配列の{「イ」}番目の要素です")上記のプログラムの「ア」と「イ」の部分にはどのようなコードを入れればよいでしょうか？
答え：ア：range(length)、イ：i+1
list1 = [16, 52, 31, 48, 9]
target = 31
length = len(list1)
for i in range(length): # range(0, length, 1)でも可
if list1[i] == target:
print(f"{target}は配列の{i+1}番目の要素です")for i in range(length):と書くことで、list1の要素数だけ繰り返し処理を行います。
range(数値)は、0から数値 - 1までの数値の数列を生成する関数です。そのため上記プログラムではiには順に0, 1, 2, 3, ..., length-1という数値が代入されます。
また、print(f"{target}は配列の{i+1}番目の要素です")と書くことで、targetがlist1のi番目の要素と一致する場合に、そのインデックス（i）を出力します。なお、配列のインデックスは0から始まる一方、n番目の要素を表す数字は1番目、2番目、…というように1から始まるようにする必要があります。そのため、iに1を足してi+1とすることで、期待した出力になるようにしていることに注意してください。
目的の処理をするプログラムは完成しましたが、このプログラムには冗長な部分があります。このプログラムは、配列の中に目的の数値を見つけた後も、配列の最後まで探索を続けてしまいます。配列list1は、重複する数値を含まないことを前提としているため、目的の数値が見つかった後に、また同じ数値が配列の中に見つかることは無く、無駄な処理となってしまいます（例えば、重複する数字を含まない、長さが10,000個もある配列を線形探索する際、もし配列の先頭が目的の数値であれば、残りの9,999個の要素の探索は無駄な処理となってしまいます）。
そのため、目的の数値が見つかった時点で探索を終了するようにプログラムを修正しましょう。
list1 = [16, 52, 31, 48, 9]
target = 31
length = len(list1)
for i in range(length):
if list1[i] == target:
print(f"{target}は配列の{i+1}番目の要素です")
break # 目的の数値が見つかった場合、探索を終了するfor文では、break句を使うことで、繰り返し処理を途中で終了することができます。breakを使用すると、for文の繰り返し処理を途中で終了し、for文の次の順次処理に即座に移ります（上記プログラムではfor文の処理の次には何も無いので、プログラムが終了します）。
上記のプログラムでは、if文を用いて目的の数値が見つかった場合にbreakを実行することで、目的の数値が見つかった時点でfor文を終了させ、探索を終えるようにしています。
また、繰り返し処理を終了するのではなく、即座に次の繰り返し処理に移るcontinue句もあります。continue句を使うと、continue句の後の処理をスキップして、次の繰り返し処理に移ります。continue句を使うことで、特定の条件を満たす場合に処理をスキップすることができます。
今回は「線形探索」の実装を通して、探索のアルゴリズムについて学びました。
線形探索はデータの先頭から順番に探索していく方法であり、データが整列されていない場合や、データの中に目的のデータが少ない場合に有効な探索方法です。
また、プログラミングにおいてアルゴリズムを作成する際には、単純に目的の処理を行うだけでなく、冗長な処理を省き、プログラムを最適化することも重要です。線形探索のプログラムも、目的の数値が見つかった時点で探索を終了するようにすることで、より効率的になりました。探索アルゴリズムには二分探索など、さらに効率的な手法が存在するため、これらを学び適切に活用することも重要です。