線形探索と二分探索の例題

3.1 線形探索を用いた配列内の要素の検索

課題: 数字の配列が与えられています。線形探索を用いて指定された数字のインデックスを見つける必要があります。数字が見つからない場合、-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
result = linear_search(arr, target)
print(f"エレメント {target} はインデックス {result} に見つかりました")  # 出力: エレメント 7 はインデックス 2 に見つかりました

# 配列にない要素の使用例:
target = 5
result = linear_search(arr, target)
print(f"エレメント {target} はインデックス {result} に見つかりました")  # 出力: エレメント 5 はインデックス -1 に見つかりました

説明:

• linear_search 関数は、配列 arr の各要素を target と比較します。
• 要素が見つかった場合、インデックスを返します。
• すべての要素が確認され、指定された値が見つからない場合、関数は -1 を返します。

ステップバイステップ:

1. 配列 [4, 2, 7, 1, 9, 3] と検索対象の値 7。
2. 検索開始: 最初の要素 (4) と 7 を比較 — 一致しません。
3. 次の要素 (2) へ — 一致しません。
4. 次の要素 (7) へ — 一致します。
5. インデックス 2 を返します。

3.2 二分探索を用いた整列された配列内の要素の検索

課題: 整列された数字の配列が与えられています。二分探索を用いて指定された数字のインデックスを見つける必要があります。数字が見つからない場合、-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
result = binary_search(sorted_array, target)
print(f"エレメント {target} はインデックス {result} に見つかりました")  # 出力: エレメント 7 はインデックス 3 に見つかりました

# 配列にない要素の使用例:
target = 6
result = binary_search(sorted_array, target)
print(f"エレメント {target} はインデックス {result} に見つかりました")  # 出力: エレメント 6 はインデックス -1 に見つかりました

説明:

• binary_search 関数は、配列 arr 内の検索範囲を追跡するために2つのポインタ（leftとright）を使用します。
• 各イテレーションで、配列の中央の要素を見つけて target と比較します。
• 中央の要素が target と等しい場合、そのインデックスを返します。
• target が中央の要素より小さい場合、探索は配列の左半分で続けられます。
• target が中央の要素より大きい場合、探索は配列の右半分で続けられます。
• 境界が交差し、要素が見つからない場合、-1を返します。

ステップバイステップ:

1. 整列された配列 [1, 3, 5, 7, 9, 11, 13] と検索対象の値 7。
2. 初期の検索範囲: left = 0, right = 6。
3. 中央の要素を探す: mid = (0 + 6) // 2 = 3。
4. 中央の要素 (7) を target (7) と比較 — 一致します。
5. インデックス 3 を返します。

3.3 様々な課題に対する適切な探索アルゴリズムの比較と選択

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

適切なアルゴリズムの選択

線形探索:

• データがソートされていないときに使用。
• 小規模な配列やリストに適しています。
• 要素数が少なく、実行時間が重要でない場合に使用。

二分探索:

• データがソートされているときに使用。
• 検索速度が重要な大きな配列に最適です。
• 同じデータセットで頻繁に検索する必要がある場合に効率的（事前にデータをソートできます）。

3.4 理解を深めるための実践的な課題

課題 1: 線形探索

数字の配列が与えられています。線形探索を用いて指定された数字を検索する関数を書いてください。関数は見つかった要素のインデックスまたは要素が見つからない場合は-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
result = linear_search(arr, target)
print(f"エレメント {target} はインデックス {result} に見つかりました")  # 出力: エレメント 7 はインデックス 2 に見つかりました

# 追加テスト:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

課題 2: 二分探索

整列された数字の配列が与えられています。二分探索を用いて指定された数字を検索する関数を書いてください。関数は見つかった要素のインデックスまたは要素が見つからない場合は-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
result = binary_search(sorted_array, target)
print(f"エレメント {target} はインデックス {result} に見つかりました")  # 出力: エレメント 7 はインデックス 3 に見つかりました

# 追加テスト:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

課題 3: 線形探索と二分探索の比較

数字の配列が与えられています。指定された数字を検索するために、線形探索を使用した関数と二分探索を使用した関数の2つを書いてください。大規模な配列で両関数のパフォーマンスを比較します。

例:

import time
import random

# 線形探索
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -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

# 大規模な配列の生成
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# パフォーマンスの比較
start_time = time.time()
linear_search(large_array, target)
print(f"線形探索にかかった時間: {time.time() - start_time:.6f} 秒")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"二分探索にかかった時間: {time.time() - start_time:.6f} 秒")