線形探索と二分探索についてウィキペディアにPythonのコード例がなかったので書いてみました。
線形探索
対象を端から順番に探していく方法です。
ここでは配列（リスト）の要素を探しインデックス（ゼロから数えて何番目）を返します。
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return - 1
for i in range(len(arr)):
if arr[i] == target:
return i
return - 1
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
result = linear_search(arr, target)
print(result)
target = 7
result = linear_search(arr, target)
print(result)
結果
7
二分探索
対象を半分ずつにして探していく方法です。
前提として配列（リスト）はソートされている必要があります。
左端と右端のインデックスの平均を中央のインデックスとします。
一致すればそれを返します。
目標よりも小さければ左端を中央の右隣にして繰り返します。
目標よりも大きければ右端を中央の左隣りにして繰り返します。
def binary_search(arr, target):
index_left = 0
index_right = len(arr) - 1
while index_left <= index_right:
index_mid = (index_left + index_right) // 2
if arr[index_mid] == target:
return index_mid
elif arr[index_mid] < target:
index_left = index_mid + 1
else:
index_right = index_mid - 1
return - 1
index_left = 0
index_right = len(arr) - 1
while index_left <= index_right:
index_mid = (index_left + index_right) // 2
if arr[index_mid] == target:
return index_mid
elif arr[index_mid] < target:
index_left = index_mid + 1
else:
index_right = index_mid - 1
return - 1
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
result = binary_search(arr, target)
print(result)
target = 7
result = binary_search(arr, target)
print(result)
結果
7
コメント