線形探索
Pythonのenumerate()関数を使うと、forループの中でリスト(配列)などのイテラブルオブジェクトの要素と同時にインデックス番号(カウント、順番)を取得できる。
計算時間 O(n)
def linear_search(li,ans):
print(str(ans) + "を検索します")
for i,data in enumerate(li):
if data == ans:
print(str(i)+ "番目にありました")
break
else:
print("入力した要素は存在しませんでした")
if __name__ == '__main__':
li=[1,4,5,6,8,9,14,19]
print("調べるリスト")
print(li)
search_num = int(input("上のリストから調べたい要素を入力してください"))
linear_search(li, search_num)
二分探索
計算時間 O ( log₂n )
def binary_search(li, ans):
low = 0
high = len(li) - 1
# 探索の下限のlowが上限のhighになるまで探索します。
while low <= high:
mid = (low + high) // 2 # 中央値
guess = li[mid]
if guess == ans:
return mid
if guess > ans:
high = mid - 1
else:
low = mid + 1
return None
li = [i for i in range(1,101)]
print(binary_search(li, 3))
print(binary_search(li, -1))