Python二分法查找算法详解：循环与递归实现

不晚

发布时间：2026-10-15| 3人浏览过

原创

本文详细介绍Python中二分法查找的实现原理与代码。通过1000页书籍查找示例解析核心思路，分别展示使用while循环和递归函数两种方式的Python代码实现。对比分析两种方法的执行效率，帮助开发者掌握这一高效查找算法。

二分法查找原理与思路

前言：

二分查找（Binary Search）是一种高效的查找算法。

假设公司新入职一名员工张三，他是公司的第47号员工。一段时间后，部分员工离职，张三的编号不再对应第47位。此时，如何快速确定张三当前的具体排名？下面我们将利用二分法来定位他的位置。

思路：

假设有一本1000页的书，随机指定一个目标页码，如何以最快方式找到它？如果逐页查找，最多可能需要1000次操作。利用二分法可以大幅减少查找次数，其核心在于“二分”策略。

步骤1：设定一个中间页码作为中心点，将1000页分为两部分。中位数的作用是每次将查找范围缩小一半，从而实现类似开方的效率提升。计算公式为：(起始页码 + 结束页码) / 2 = 中间页码。

步骤2：将目标页码与中间页码进行比较。若目标页码大于中间页码，则舍弃前半部分，继续在后半部分查找；反之，则舍弃后半部分，在前半部分查找，以此达到缩小范围的效果。步骤3：在新的查找范围内重新计算中间页码。

步骤4：将目标页码与新计算的中间页码对比，确定新的查找范围。

步骤5：循环执行上述步骤，直到找到目标页码为止。

Python代码实现

代码：

基于上述思路，我们首先通过循环方式实现二分查找。

#模拟页码
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#首位值
low = 0
#末位值
height = len(array)-1
#设定查找页码
findNum = 1
 
#循环查找
while True:
    #获取中位数
    mid = int((low+height)/2)
    #打印中位数,查看循环次数
    print(array[mid])
    #如果中位数小于查找值,则锁定后半段
    if array[mid] < findNum:
        #重置低位数
        low = mid + 1
    #如果中位数大于查找值,则锁定前半段
    elif array[mid] > findNum:
        #重置高位值
        height = mid - 1
    #找到数字则打印该值下标,终止循环
    elif array[mid]==findNum:
        print('find it:',array[mid],' index:',mid)
        break

除了循环方式外，还可以使用递归实现，代码结构更为简洁。

array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
 
#函数递归
#定义一个函数,给三个形参:低位值，高位值，查找值
def BinarySearch(low,height,findNum):
    #计算出中位数
    middle = (low+height)//2
    #如果中位数小于查找值,则锁定后半段
    if findNum >array[middle]:
        #重置低位数
        low = middle +1
    #如果中位数大于查找值,则锁定前半段
    elif findNum<array[middle]:
        #重置高位值
        height = middle - 1
    else:
        #找到该值并返回
        return '该值下标为:%s,值为:%s'%(middle,array[middle])
    #没有找到则调用自身继续查找
    return BinarySearch(low,height,findNum)
 
print(BinarySearch(array[0],len(array)-1,19))