【Python】第7章第6回：線形探索と二分探索

本記事では、Pythonを用いた線形探索と二分探索のアルゴリズムについて解説します。それぞれの特徴と使い分けを理解し、効率的なデータ探索手法を学びましょう。

0. 記事の概要

この記事を読むメリット

• 探索アルゴリズムの理解：線形探索と二分探索の違いと使い分けを学べます。
• Pythonでの実装力向上：探索アルゴリズムをPythonコードで実践できます。
• 効率的なデータ処理：大規模なデータセットでの探索効率を向上できます。

この記事で学べること

• 線形探索と二分探索の基礎知識
• Pythonでのアルゴリズム実装方法
• 探索アルゴリズムの適切な選択方法

1. 線形探索とは？

1.1 線形探索の基本

線形探索（Linear Search）は、リストや配列の要素を最初から順番に調べ、目的の値を見つける単純な探索手法です。

主な特徴:

• データがソートされていなくても使用可能
• 時間計算量はO(n)
• 小規模データに適している

1.2 線形探索の実例

# 線形探索の実装
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i  # 目的の値が見つかった場合、そのインデックスを返す
    return -1  # 見つからなかった場合は-1を返す

numbers = [10, 20, 30, 40, 50]
target = 30
result = linear_search(numbers, target)
print(f"結果: {result}")

動作解説

1. リストの各要素を順番にチェックします。
2. 一致する値が見つかればそのインデックスを返します。
3. リストを最後まで調べても見つからなければ-1を返します。

2. 二分探索とは？

2.1 二分探索の基本

二分探索（Binary Search）は、ソート済みのリストを対象に、高速な探索を行うアルゴリズムです。データを半分に分割しながら探索を進めます。

主な特徴:

• データがソートされている必要がある
• 時間計算量はO(log n)
• 大規模データに適している

2.2 二分探索の実例

# 二分探索の実装
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 目的の値が見つかった場合、そのインデックスを返す
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 見つからなかった場合は-1を返す

numbers = [10, 20, 30, 40, 50]
target = 30
result = binary_search(numbers, target)
print(f"結果: {result}")

動作解説

1. リストの中央値を取得します。
2. 目的の値が中央値より小さい場合、探索範囲を左半分に絞ります。
3. 目的の値が中央値より大きい場合、探索範囲を右半分に絞ります。
4. 中央値と一致すれば、そのインデックスを返します。
5. 範囲がなくなれば探索失敗として-1を返します。

3. 線形探索と二分探索の比較

3.1 時間計算量の比較

以下は両アルゴリズムの時間計算量の違いを示した表です。

アルゴリズム	時間計算量	データの要件
線形探索	O(n)	ソート不要
二分探索	O(log n)	ソート済み

4. 練習問題

以下の課題に挑戦してみましょう。

1. 線形探索を用いてリスト内の最大値を探す関数を作成してください。
2. 二分探索を用いてリスト内の特定の値を探すプログラムを書いてください。
3. 線形探索と二分探索のパフォーマンスを比較するコードを作成してください。

5. 練習問題の解答と解説

問1〜3の解答例

# 問1: 線形探索で最大値を探す
def find_max(arr):
    max_value = arr[0]
    for value in arr:
        if value > max_value:
            max_value = value
    return max_value

numbers = [10, 20, 30, 40, 50]
print(f"最大値: {find_max(numbers)}")

# 問2: 二分探索で特定の値を探す
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

numbers = [10, 20, 30, 40, 50]
print(f"結果: {binary_search(numbers, 30)}")

# 問3: パフォーマンス比較
import time

# 線形探索
start_time = time.time()
find_max(numbers)
end_time = time.time()
print(f"線形探索の処理時間: {end_time - start_time:.5f}秒")

# 二分探索
numbers.sort()
start_time = time.time()
binary_search(numbers, 30)
end_time = time.time()
print(f"二分探索の処理時間: {end_time - start_time:.5f}秒")

6. まとめ

本記事では、線形探索と二分探索の基本的な使い方と特徴について学びました。用途に応じてこれらを使い分け、効率的なデータ探索を行いましょう。