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