Python 二分探索
二分探索は、ソート済み配列から特定の要素を探す検索アルゴリズムです。検索プロセスは配列の中央の要素から始まり、中央の要素が探している要素と一致すれば検索は終了します。特定の要素が中央の要素より大きいか小さい場合は、配列の中で中央の要素より大きい部分または小さい部分で検索を行い、最初と同じように中央の要素から比較します。あるステップで配列が空になった場合は、見つからなかったことを意味します。この検索アルゴリズムは、比較のたびに検索範囲を半分に縮めます。
例：再帰
# x の arr 内のインデックスを返す。存在しない場合は -1 を返す
def binarySearch (arr, l, r, x):
# 基本チェック
if r >= l:
mid = int(l + (r - l)/2)
# 要素がちょうど中央位置にある場合
if arr[mid] == x:
return mid
# 要素が中央の位置の要素より小さい場合、左側の要素だけを比較すればよい
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# 要素が中央の位置の要素より大きい場合、右側の要素だけを比較すればよい
else:
return binarySearch(arr, mid+1, r, x)
else:
# 存在しない
return -1
# テスト配列
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# 関数呼び出し
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("要素の配列内のインデックスは %d" % result )
else:
print ("要素は配列内にありません")
上記のコードを実行すると、出力結果は次のとおりです：
元素在数组中的索引为 3その他の拡張