写一个二分法

二分法，也称为折半查找，是一种在有序数组中查找特定元素的算法。它通过将数组分成两个部分来减少搜索的范围，然后递归地在其中一个部分中查找目标值。

以下是一个简单的二分法实现：

def binary_search(arr, val):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == val:
            return mid
        elif arr[mid] < val:
            low = mid + 1
        else:
            high = mid - 1

    return -1

这个函数接受一个有序数组和一个要查找的值作为参数。它通过将数组的左边界和右边界保存在 low 和 high 变量中来初始化搜索范围。然后，它在一个循环中进行搜索，直到找到目标值或者搜索范围缩小到空集。

在每次循环中，算法计算中间元素的索引 mid，并将其与目标值进行比较。如果它们相等，那么函数返回 mid，表示找到了目标值。如果 arr[mid] 小于目标值，那么目标值只可能在 arr[mid+1:high+1] 中，因此将搜索范围缩小到右半部分。否则，目标值只可能在 arr[low:mid] 中，因此将搜索范围缩小到左半部分。

如果函数在循环结束时仍然没有找到目标值，那么它返回 -1 表示未找到。

例如，如果我们使用以下代码来调用这个函数：

arr = [1, 3, 5, 7, 9]
val = 5

print(binary_search(arr, val))

那么输出将是 2，表示目标值 5 在数组中的索引为 2