pythonの二分探索アルゴリズムの書き方

2年 ago
蓮, 翼
1 minute

以下是一个用Python实现二分查找的代码示例：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
  
    while low <= high:
        mid = (low + high) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
  
    return -1

# 测试代码
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 10
result = binary_search(arr, target)
if result != -1:
    print("元素在索引位置", result)
else:
    print("元素不在数组中")

在此示例中，我们定义了一个名为binary_search的函数，该函数接受一个已排序的数组arr和目标值target作为参数。然后，我们使用low和high两个指针分别指向数组的最低和最高索引。

その後、目標の値が見つかるか、lowがhighより大きくなるまでループで反復します。各反復では、中間インデックスmidを算出し、目標の値と比較します。arr[mid]が目標の値と等しければ、midを結果として返します。arr[mid]が目標の値より小さい場合は、lowポインタをmid + 1 に移動し、そうでない場合は highポインタをmid – 1 に移動します。

循環の終了時にターゲット要素が見つからない場合は、配列にターゲット要素が存在しないことを示す -1 を返します。

最後にテストコードを使用してbinary_search関数が正しく動作していることを検証し、結果を出力する。このサンプルでは目的の要素10は配列のインデックス位置4にある。目的の要素が配列中に存在しない場合は「要素は配列内にありません」と出力する。

bannerAds