利用python实现二分查找

二分查找是一种高效的查找算法，它利用了有序数组的特性，每次可以将查找范围缩小一半。以下是使用Python实现二分查找的代码：

def binary_search(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  # 未找到目标值

以上代码中，`arr`为有序数组，`target`为目标值。首先，初始化左右边界为数组的第一个和最后一个元素的下标，然后进入循环。每次循环会计算中间位置`mid`，并判断`arr[mid]`与`target`的大小关系，如果相等则返回`mid`，如果`arr[mid]`小于`target`则目标值在右半部分，左边界更新为`mid+1`，否则目标值在左半部分，右边界更新为`mid-1`。如果循环结束仍未找到目标值，则返回-1。