编写·算法实现二分检索

二分检索（Binary Search）是一种高效的查找算法，通常用于在有序数组中查找某个元素的位置。其基本思想是将数组分为两半，如果目标元素小于数组中间的元素，则在左半部分继续查找；反之，在右半部分查找。重复这个过程直到找到目标元素或者确定目标元素不存在。

以下是使用 Python 实现二分检索的示例代码：

def binary_search(arr, target):
    """
    在有序数组 arr 中查找目标元素 target 的位置
    :param arr: 有序数组
    :param target: 目标元素
    :return: 目标元素在数组中的位置，若不存在则返回 -1
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

在这个实现中，我们使用了两个指针 `left` 和 `right` 来表示当前搜索区间的左右边界，初始值分别为数组的第一个和最后一个元素的下标。在每一轮循环中，我们计算出中间元素的下标 `mid`，然后将目标元素和中间元素比较。如果相等，则直接返回中间元素的下标；如果目标元素较大，则在右半部分继续查找，更新左边界为 `mid+1`；否则，在左半部分查找，更新右边界为 `mid-1`。

由于每一轮循环都会缩小搜索区间的大小为原来的一半，因此二分检索的时间复杂度为 $O(\log n)$，其中 $n$ 是数组的长度。