037. 编写一个函数，实现二分查找算法

二分查找算法是一种高效的查找算法，适用于在有序数组中查找特定元素。其基本思想是通过不断将数组分为两半，逐步缩小查找范围，直到找到目标元素或确定目标元素不存在。

示例代码

def binary_search(arr, target):
    """
    使用二分查找算法在有序数组 arr 中查找目标值 target。

    参数:
        arr (list): 有序数组。
        target (int): 要查找的目标值。

    返回:
        int: 如果找到目标值，返回其在数组中的索引；否则返回 -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  # 未找到目标值

# 测试代码
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15]
target_value = 9

result = binary_search(sorted_array, target_value)

if result != -1:
    print(f"目标值 {target_value} 在数组中的索引为 {result}。")
else:
    print(f"目标值 {target_value} 不在数组中。")

运行结果

运行上述代码后，输出如下：

目标值 9 在数组中的索引为 4。

代码解释

初始化指针：

定义两个指针 left 和 right，分别指向数组的起始位置和结束位置。

循环条件：

使用 while left <= right 作为循环条件，确保查找范围有效。

计算中间索引：

使用 (left + right) // 2 计算中间索引 mid。

比较中间值：

如果 arr[mid] == target，说明找到了目标值，返回其索引。
如果 arr[mid] < target，说明目标值在右侧子数组中，更新 left 为 mid + 1。
如果 arr[mid] > target，说明目标值在左侧子数组中，更新 right 为 mid - 1。

返回结果：

如果循环结束仍未找到目标值，返回 -1，表示目标值不在数组中。

扩展：递归实现

二分查找算法也可以通过递归实现。以下是一个递归版本的二分查找函数：

def binary_search_recursive(arr, target, left, right):
    """
    使用递归实现二分查找算法。

    参数:
        arr (list): 有序数组。
        target (int): 要查找的目标值。
        left (int): 当前查找范围的左边界。
        right (int): 当前查找范围的右边界。

    返回:
        int: 如果找到目标值，返回其在数组中的索引；否则返回 -1。
    """
    if left > right:
        return -1  # 未找到目标值

    mid = (left + right) // 2  # 计算中间索引

    if arr[mid] == target:
        return mid  # 找到目标值，返回索引
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # 目标值在右侧子数组
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # 目标值在左侧子数组

# 测试代码
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15]
target_value = 9

result = binary_search_recursive(sorted_array, target_value, 0, len(sorted_array) - 1)

if result != -1:
    print(f"目标值 {target_value} 在数组中的索引为 {result}。")
else:
    print(f"目标值 {target_value} 不在数组中。")

注意事项

数组必须有序：二分查找算法要求输入数组必须是有序的（通常是升序）。如果数组无序，需要先对数组进行排序。
性能：二分查找的时间复杂度为 O(logn)，其中 n 是数组的长度。这使得二分查找在处理大规模数据时非常高效。
边界条件：在实现二分查找时，需要注意边界条件的处理，避免数组索引越界。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)