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

4.1 線形探索と二分探索の時間計算量の比較

線形探索と二分探索の時間計算量を比較してみよう。

線形探索:

• 時間計算量: O(n)、ここでnは配列またはリストの要素数。
• ベストケース: O(1) — 要素が最初に見つかる。
• 平均ケース: O(n/2) = O(n) — 要素が平均的に中央付近で見つかる。
• ワーストケース: O(n) — 要素が最後に見つかるか、存在しない。

二分探索:

• 時間計算量: O(log n)、ここでnは配列またはリストの要素数。
• ベストケース: O(1) — 要素が最初のステップで見つかる（中央要素）。
• 平均ケース: O(log n) — ソートされた配列での探索。
• ワーストケース: O(log n) — 要素が最後のステップで見つかるか、存在しない。

時間計算量の分析例

線形探索:

• 配列 [1, 3, 5, 7, 9, 11, 13]、探す要素は7。
• 7がインデックス3で見つかるまで各要素を確認。
• 4回の確認が必要で、これはO(n)に相当する。

二分探索:

• 配列 [1, 3, 5, 7, 9, 11, 13]、探す要素は7。
• 中央要素（7）が最初のステップで見つかる。
• 1回の確認が必要で、これはO(log n)に相当する。

4.2 各メソッドのメリットとデメリット

それぞれの探索方法のメリットとデメリットを見てみよう。

線形探索:

メリット:

• 実装の簡単さ: 線形探索は非常に簡単に実装できて理解しやすい。
• データの要件なし: 線形探索はソートされていないデータにも使える。
• 小さな配列に適している: 線形探索は小規模な配列では効果的。

デメリット:

• 大きな配列には低効率: 時間計算量O(n)は大きな配列に対して非効率的。
• 実行時間が長い: 大きな配列では、特に探す要素が配列の終わりに近いか存在しない場合、線形探索に多くの時間がかかる。

二分探索:

メリット:

• 大きな配列に高効率: 時間計算量O(log n)は大規模な配列で非常に効率的。
• 高速な実行: 二分探索は大規模なソートされた配列において線形探索よりもかなり速い。

デメリット:

• ソートされたデータの要件: 二分探索はソートされた配列でのみ動作し、事前にソートするのに追加の時間がかかる場合がある。
• 実装の複雑さ: 二分探索の実装は線形探索に比べて複雑。

4.3 どの探索を使うべきか

線形探索と二分探索を使う場面を考えてみよう。

線形探索。

次の場合は線形探索を使用してください:

• 配列またはリストがソートされていない。
• 配列またはリストのサイズが小さい。
• ソートに追加のコストをかけずにシンプルかつ迅速な解決策が必要。
• 最初の出現またはすべての出現を見つけたい。
• データがリアルタイムでやってきて、事前のソートが不可能または不適切。

二分探索。

次の場合は二分探索を使用してください:

• 配列またはリストがソートされている。
• 配列またはリストのサイズが大きい。
• 同じデータセットで頻繁に要素を検索する（データを一度だけ事前にソートできる）。
• 探索速度が非常に重要。
• データの事前ソートに時間をかけても構わない。

4.4 線形探索の課題例

1. ソートされていないリストでの探索

ソートされていない数字のリストで指定された数字のインデックスを見つける必要があります。

例:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # 出力: 2

2. 配列内の最初の出現を探索

文字列のリストで指定された要素の最初の出現を見つける必要があります。

例:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target))  # 出力: 1

3. リアルタイムデータでの探索

リアルタイムでやってくるデータストリームで要素を見つける。

例:

import random

def find_in_stream(stream, target):
    for index, element in enumerate(stream):
        if element == target:
            return index
    return -1

stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))

4.5 二分探索の課題例

1. ソートされた配列での探索

ソートされた数字の配列で指定された数字のインデックスを見つける必要があります。

例:

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

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # 出力: 3

2. 大きなデータセットでの頻繁な探索

大規模なソート済み配列で頻繁に要素を探索。

例:

import random

sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))

3. ソートされたデータベースでの要素探索

キーとなるフィールドでソートされたデータベースでレコードを見つける。

例:

database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
    left, right = 0, len(db) - 1
    while left <= right:
        mid = (left + right) // 2
        if db[mid]["id"] == target_id:
            return db[mid]
        elif db[mid]["id"] < target_id:
            left = mid + 1
        else:
            right = mid - 1
    return None

target_id = 54321
print(binary_search_db(database, target_id))