探索アルゴリズム

1
# 線形探索の実装
2
def linear_search(arr, target):
3
    for i in range(len(arr)):
4
        if arr[i] == target:
5
            return i
6
    return -1
7

8
# 使用例
9
arr = [11, 23, 35, 47, 59, 71]
10
target = 47
11
result = linear_search(arr, target)
12
print(f"見つかった位置: {result}")  # 見つかった位置: 2

1
# 二分探索の実装
2
def binary_search(arr, target):
3
    left = 0
4
    right = len(arr) - 1
5
    while left <= right:
6
        mid = (left + right) // 2
7
        if arr[mid] == target:
8
            return mid
9
        elif arr[mid] < target:
10
            left = mid + 1
11
        else:
12
            right = mid - 1
13
    return -1
14

15
# 使用例
16
arr = [11, 23, 35, 47, 59, 71]
17
target = 47
18
result = binary_search(arr, target)
19
print(f"見つかった位置: {result}")  # 見つかった位置: 2

1
# 探索アルゴリズムの比較
2
import time
3

4
arr = list(range(10000))
5
target = 9999
6

7
# 線形探索
8
start = time.time()
9
linear_search(arr, target)
10
end = time.time()
11
print(f"線形探索: {end - start:.6f}秒")
12

13
# 二分探索
14
arr.sort()  # ソート済みの配列
15
start = time.time()
16
binary_search(arr, target)
17
end = time.time()
18
print(f"二分探索: {end - start:.6f}秒")

1
# 探索アルゴリズムの使用例
2
# データベースの検索
3
users = [
4
    {"id": 1, "name": "Alice", "email": "alice@example.com"},
5
    {"id": 2, "name": "Bob", "email": "bob@example.com"},
6
    {"id": 3, "name": "Charlie", "email": "charlie@example.com"},
7
]
8

9
# 線形探索でユーザーを検索
10
target_id = 2
11
found_user = None
12
for user in users:
13
    if user["id"] == target_id:
14
        found_user = user
15
        break
16

17
if found_user:
18
    print(f"ユーザーが見つかりました: {found_user['name']}")
19
else:
20
    print("ユーザーが見つかりませんでした")
21

22
# 二分探索でユーザーを検索（IDでソート済みと仮定）
23
sorted_users = sorted(users, key=lambda x: x["id"])
24
target_id = 2
25
found_user = binary_search(sorted_users, target_id)
26

27
if found_user != -1:
28
    print(f"ユーザーが見つかりました: {sorted_users[found_user]['name']}")
29
else:
30
    print("ユーザーが見つかりませんでした")