🐍
Python アルゴリズム学習 Day 1：線形探索アルゴリズム
はじめに
こちらの記事は Python を使ったアルゴリズム学習記録です。
今回は線形探索アルゴリズムと、それを実装するための基本的な Python のリスト操作について紹介します。
本記事の完全なソースコードはgithub リポジトリを参照してください。
Python のリスト操作🔰
Python のリストは、他の言語における配列に相当するデータ構造です。線形探索を実装する前に、基本的なリスト操作を確認しておきます。
# リストの作成
numbers = [1, 2, 3, 4, 5]
print(f"作成したリスト: {numbers}")
# リストの要素へのアクセス
print(f"インデックス2の要素: {numbers[2]}")
# リストへの要素追加
numbers.append(6)
print(f"要素追加後: {numbers}")
# リストからの要素削除
numbers.remove(3) # 値が3の要素を削除
print(f"要素削除後: {numbers}")
# リストの長さ
print(f"リストの長さ: {len(numbers)}")
# リスト内に要素が存在するかの確認
print(f"値4はリスト内に存在するか: {4 in numbers}")
print(f"値10はリスト内に存在するか: {10 in numbers}")
実行結果：
作成したリスト: [1, 2, 3, 4, 5]
インデックス2の要素: 3
要素追加後: [1, 2, 3, 4, 5, 6]
要素削除後: [1, 2, 4, 5, 6]
リストの長さ: 5
値4はリスト内に存在するか: True
値10はリスト内に存在するか: False
Python のリストは非常に柔軟で使いやすいデータ構造です。要素の追加、削除、アクセスが簡単にできるため、様々なアルゴリズムを実装する際の基礎となります。
線形探索アルゴリズム
線形探索は、配列の先頭から順に各要素を調べていき、目的の値を探すシンプルなアルゴリズムです。
def linear_search(arr, target):
"""
線形探索アルゴリズム
Parameters:
arr (list): 探索対象の配列
target: 探索する値
Returns:
int: 見つかった場合はそのインデックス、見つからなかった場合は-1
"""
for i in range(len(arr)):
if arr[i] == target:
return i # 見つかった場合、インデックスを返す
return -1 # 見つからなかった場合、-1を返す
実際に使ってみましょう：
# テスト用のデータセット
numbers = [10, 25, 3, 14, 42, 19, 7, 36]
# 配列内の値を探す
target = 14
result = linear_search(numbers, target)
if result != -1:
print(f"値 {target} はインデックス {result} で見つかりました。")
else:
print(f"値 {target} は配列内に存在しません。")
# 配列内に存在しない値を探す
target = 100
result = linear_search(numbers, target)
if result != -1:
print(f"値 {target} はインデックス {result} で見つかりました。")
else:
print(f"値 {target} は配列内に存在しません。")
実行結果：
値 14 はインデックス 3 で見つかりました。
値 100 は配列内に存在しません。
拡張：複数の一致を検索
基本的な線形探索は最初に見つかった要素のインデックスを返しますが、すべての一致を見つけたい場合もあります。そこで、linear_search_all関数を実装してみました。
def linear_search_all(arr, target):
"""
線形探索アルゴリズム（すべての一致を検出）
Parameters:
arr (list): 探索対象の配列
target: 探索する値
Returns:
list: 見つかった場合はそのインデックスのリスト、見つからなかった場合は空リスト
"""
found_indices = []
for i in range(len(arr)):
if arr[i] == target:
found_indices.append(i)
return found_indices
使用例：
# 重複した要素を含むリスト
numbers = [5, 10, 15, 20, 10, 25, 30, 10]
# 値10のすべての出現位置を検索
target = 10
result = linear_search_all(numbers, target)
if result:
print(f"値 {target} は以下のインデックスで見つかりました: {result}")
else:
print(f"値 {target} は配列内に存在しません。")
実行結果：
値 10 は以下のインデックスで見つかりました: [1, 4, 7]
まとめ
初日の学習では、線形探索アルゴリズムとそれを実装するための Python のリスト操作について学びました。線形探索は最もシンプルな探索アルゴリズムですが、小さなデータセットや一度だけ検索する場合には十分実用的です。
線形探索アルゴリズムの特徴：
- 実装が非常に簡単
- 整列されていないデータでも使用可能
- 最悪の場合、配列のすべての要素を確認する必要がある (O(n)の時間計算量)
Discussion