python笔记4：使用python实现二分查找（While循环和递归）

概念

二分查找（Binary Search），也称为折半查找，是一种高效的查找算法，用于在有序数组（如按升序或降序排列的数组）中查找特定元素的位置。

原理

假设我们要在一个升序排列的数组 arr中查找目标值 target，二分查找的原理如下：

• 初始化指针：设置两个指针，left指向数组的第一个元素（索引为 0），right指向数组的最后一个元素（索引为 len(arr) - 1）。
• 计算中间位置：在查找过程中，计算当前查找区间的中间位置 mid，可以使用公式 mid = (left + right) // 2 来计算。
• 比较中间元素与目标值：
  • 如果中间元素 arr[mid] 等于目标值 target，则查找成功，返回中间元素的索引 mid。
  • 如果中间元素 arr[mid] 大于目标值 target，说明目标值只可能在左半部分，因此将 right 指针更新为 mid - 1，缩小查找范围到左半部分。
  • 如果中间元素 arr[mid] 小于目标值 target，说明目标值只可能在右半部分，因此将 left 指针更新为 mid + 1，缩小查找范围到右半部分。
• 重复步骤 2 和 3：不断重复上述步骤，直到找到目标值或者查找区间为空（即 left > right）。如果查找区间为空，说明目标值不在数组中，返回 -1 表示查找失败。

时间复杂度

每次查找都将查找范围缩小一半，因此二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。

实现方式一：使用While循环

需求：

查询某个数字在列表中的位置，如果查到则返回目标位置和查询次数，如果没查到，则返回-1。

代码如下：

# 查询某个数字在列表中的位置，如果查到则返回目标位置和查询次数，如果没查到，则返回-1
# 原始列表
data_list = [3, 7, 11, 12, 27, 33, 35, 56, 79, 88, 100, 102]


def binary_search(target):
    """
    二分查找函数 - While循环
    :param target: 查询的目标数字
    :return: 目标位置和查询次数
    """
    # 初始最左侧位置
    left = 0
    # 初始最右侧位置
    right = len(data_list) - 1
    # 查询次数，默认1次
    count = 1
    # 只有当左侧位置不大于右侧位置时，才进行查询
    while left <= right:
        # 中间位置
        middle = (left + right) // 2  # 向下取整，比如 7//2 结果为3
        # 如果目标和中间数字相等，说明查到了，返回目标位置和查询次数
        if target == data_list[middle]:
            return middle, count
        # 如果目标比中间数字小，则把最右侧位置移动到中间位置的左侧1个位置
        elif target < data_list[middle]:
            right = middle - 1
        # 如果目标比中间数字大，则把最左侧位置移动到中间位置的右侧1个位置
        else:
            left = middle + 1

        # 查询次数加1
        count += 1
    # 当左侧位置大于右侧位置时，终止查询
    else:
        return -1, count


# 查询示例
def main():
    target = 66
    # 进行二分查询，并获取目标位置和查询次数
    result, search_count = binary_search(target)
    if result != -1:
        print(f'目标数字{target}在第{result}个位置，共查询{search_count}次！')
    else:
        print(f'未查到目标数字{target}，共查询{search_count}次！')


# 调用查询
main()

运行结果：

如果查询35，则运行结果为：

目标数字35在第6个位置，共查询3次！

如果查询66，则运行结果为：

未查到目标数字66，共查询5次！

Tips:

如果不需要记录查询次数，则把代码中count相关的变量去掉就可以。

实现方式二：递归

需求：

查询某个数字在列表中的位置，如果查到则返回目标位置，如果没查到，则返回-1。

代码如下：

# 查询某个数字在列表中的位置，如果查到则返回目标位置，如果没查到，则返回-1
# 原始列表
data_list = [3, 7, 11, 12, 27, 33, 35, 56, 79, 88, 100, 102]


def binary_search(left, right, target):
    """
    二分查找 - 递归
    :param left: 查询最左侧位置
    :param right: 查询最右侧位置
    :param target: 目标数字
    :return: 目标位置
    """
    # 当左侧位置大于右侧位置时，终止查询。（递归出口）
    if left > right:
        return -1
    # 中间位置
    middle = (left + right) // 2  # 向下取整，比如 7//2 结果为3
    # 如果目标和中间数字相等，说明查到了，返回目标位置
    if target == data_list[middle]:
        return middle
    # 如果目标比中间数字小，则把最右侧位置移动到中间位置的左侧1个位置
    elif target < data_list[middle]:
        right = middle - 1
    # 如果目标比中间数字大，则把最左侧位置移动到中间位置的右侧1个位置
    else:
        left = middle + 1
    # 递归调用二分查找函数，并把结果返回
    return binary_search(left, right, target)


# 查询示例
def main():
    # 初始最左侧位置
    left = 0
    # 初始最右侧位置
    right = len(data_list) - 1
    target = 35
    # 进行二分查询，并获取目标位置
    result = binary_search(left, right, target)
    if result != -1:
        print(f'目标数字{target}在第{result}个位置！')
    else:
        print(f'未查到目标数字{target}！')


# 调用查询
main()

运行结果：

如果查询35，则运行结果为：

目标数字35在第6个位置！

如果查询66，则运行结果为：

未查到目标数字66！

Have fun!