Pythonで線形探索と二分探索

Pocket

線形探索と二分探索についてウィキペディアにPythonのコード例がなかったので書いてみました。

線形探索

対象を端から順番に探していく方法です。
ここでは配列(リスト)の要素を探しインデックス(ゼロから数えて何番目)を返します。

def linear_search(arr, target):
  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)

結果
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
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
result = binary_search(arr, target)
print(result)

結果
7

[ 2024年2月6日 | カテゴリー: Python | タグ: , ]

« | »

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報