発展課題：探索

ここからはちょっと脱線。

Pythonらしいプログラム。でも先進的な言語機能を利用しており共通テスト対策としては不適切。

def lsearch(num_list, x):
    for v in num_list:
        if v == x:
            print(" 見つかりました ")
            return
    print(" 見つかりませんでした ")

lst = [20, 42, 45, 47, 44, 40, 15, 36, 6, 11, 50, 16, 29, 7, 1, 25, 31, 39, 38, 14]
v = 16
lsearch(lst, v)

次に、Pythonがとんでもない言語である片りん。

実は検索値と要素を逐次比較するプログラムを書かなくても検索ができる。ある集合の中にこの要素はあるかと聞くだけ。

num_list= [20, 42, 45, 47, 44, 40, 15, 36, 6, 11, 50, 16, 29, 7, 1, 25, 31, 39, 38, 14]
v = 16
print(v in num_list)
print(44 in num_list)

共通テスト対策にはならないけど、上記の機能を利用した関数の定義例。単純すぎて実際に関数化しないと思うけど。。。Pythonが広く利用されるようになっている理由の一つ：ある意味アルゴリズムを考えなくてもプログラムは書ける。。。ことが結構ある。

def lsearch(num_list, x):
    if x in num_list:
        print(" 見つかりました ")
    else:
        print(" 見つかりませんでした ")

lst = [20, 42, 45, 47, 44, 40, 15, 36, 6, 11, 50, 16, 29, 7, 1, 25, 31, 39, 38, 14]
v = 16
lsearch(lst, v)

再帰処理による二分探索

def binary_search(arr, target, low, high):
    if low > high:
        return -1  # ターゲットが見つからない場合
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid  # ターゲットが見つかった場合
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)  # 右半分を探索
    else:
        return binary_search(arr, target, low, mid - 1)   # 左半分を探索

lst = list(range(20))
print("lst =", lst)
print("位置 =", binary_search(lst, 12, 0, len(lst) - 1))# 例: ソートされた配列からターゲットを探索