検索アルゴリズム

データ集合から特定の要素を見つける操作です。代表的なものに線形探索と二分探索があります。

• 線形探索: 先頭から順番に各要素を比較し、目的の値が見つかるか、リストの終端に達するまで繰り返します。時間計算量はO(n)です。
• 二分探索: ソート済みの配列に対して使用されます。探索範囲の中間点の値と目的の値を比較し、探索範囲を半分ずつ狭めていきます。時間計算量はO(log n)です。

二分探索の実装例（Python）

def binary_search(data, target_value):
    low_index = 0
    high_index = len(data) - 1

    while low_index <= high_index:
        mid_index = (low_index + high_index) // 2
        if data[mid_index] == target_value:
            return mid_index
        elif data[mid_index] < target_value:
            low_index = mid_index + 1
        else:
            high_index = mid_index - 1
    return -1

# 使用例
sample_array = [2, 5, 8, 12, 16, 23, 38, 45, 56]
result = binary_search(sample_array, 23)
print(result)  # 出力: 5

グラフ探索アルゴリズム

グラフはノードとエッジからなる構造です。探索方法には深さ優先探索（DFS）と幅優先探索（BFS）があります。

• 深さ優先探索（DFS）: 可能な限り一つの経路を深く探索し、行き止まりに達したら戻って別の経路を探索します。
• 幅優先探索（BFS）: 開始ノードから近い順に、同じ深さのノードをすべて探索してから次の深さへ進みます。

深さ優先探索の実装例

graph_structure = {
    'X': ['Y', 'Z'],
    'Y': ['V', 'W'],
    'Z': ['W'],
    'V': [],
    'W': []
}

visited_nodes = set()

def depth_first_search(graph, current_node):
    if current_node not in visited_nodes:
        print(current_node)
        visited_nodes.add(current_node)
        for adjacent_node in graph[current_node]:
            depth_first_search(graph, adjacent_node)

# 使用例
depth_first_search(graph_structure, 'X')

動的計画法（DP）

大きな問題を小さな部分問題に分解し、部分問題の結果を記録（メモ化）しながら解を構築する手法です。フィボナッチ数列の計算は典型的な例です。

フィボナッチ数列のDP実装例

def compute_fibonacci(number, memory={}):
    if number in memory:
        return memory[number]
    if number <= 2:
        return 1
    memory[number] = compute_fibonacci(number-1, memory) + compute_fibonacci(number-2, memory)
    return memory[number]

# 使用例
print(compute_fibonacci(10))  # 出力: 55

ハッシュアルゴリズム

データを一定の規則（ハッシュ関数）で変換し、高速な検索を可能にする技術です。Pythonの辞書型は内部でハッシュテーブルを利用しています。

# Pythonの辞書はハッシュテーブルとして実装されている
item_dict = {
    'pen': 'stationery',
    'apple': 'fruit',
    'carrot': 'vegetable'
}
# キーによる高速な値の取得
print(item_dict['apple'])  # 出力: fruit