二分查找是一种在有序数组中定位目标值的经典算法，其核心思想是每次将搜索范围对半拆分，从而把比较次数从线性级别降到对数级别。在Python里，我们既可以用循环也可以用递归来完成这一逻辑，但无论哪种写法，都必须保证原始数据已经按升序或降序排列，否则算法失去意义。
一、二分查找的基本原理
假设有一个升序排列的列表，左边界下标为left，右边界下标为right。我们取中间位置mid = (left + right) // 2，将列表[mid]与要查找的target进行比较。如果相等，说明找到了；如果列表[mid]小于target，说明目标只可能落在右半部分，于是令left = mid + 1；反之则令right = mid - 1。如此反复，直到left大于right时仍未命中，即表示目标不存在。
这种减半收缩的方式，使得每执行一次循环，待查区间长度至少减少一半。对于有n个元素的序列，最多只需约log2(n)次比较。相比从头到尾扫描的O(n)做法，当数据量达到十万或百万级时，二分查找的优势极为明显。不过它无法应用于链表这类不支持随机下标的场景，也不能处理无序数据。
二、循环版本的Python实现
下面给出最常见的左右闭区间循环写法，区间表示为[left, right]，两端都包含。这种写法边界清晰，不容易在终止条件上出错。
def binary_search(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 测试示例
data = [1, 3, 5, 7, 9, 11]
print(binary_search(data, 7)) # 输出 3
print(binary_search(data, 4)) # 输出 -1
上述代码中，while循环条件是left <= right，因为当left与right重合时，那个唯一的元素仍需要被检查。若写成left < right，就会漏掉最后一个可能的位置。函数返回下标，调用方可以根据返回值是否大于等于0来判断查找是否成功。
该实现只使用了固定数量的变量，空间复杂度为O(1)，在大规模数据下也不会带来额外内存压力。它的缺点在于要求输入必须是列表或支持下标访问的类型，且必须预先排序，排序成本在频繁插入删除的场景中需要另行考量。
三、递归版本的Python实现
递归写法更贴近数学定义，把子区间作为参数不断向下传递。虽然逻辑直观，但每次调用都会在调用栈上占用空间，深度过大时可能触发递归限制。
def binary_search_rec(nums, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search_rec(nums, target, mid + 1, right)
else:
return binary_search_rec(nums, target, left, mid - 1)
# 测试示例
data = [2, 4, 6, 8, 10]
print(binary_search_rec(data, 8, 0, len(data) - 1)) # 输出 3
递归版本把区间边界作为实参传入，初始调用时传入0和len(nums)-1。每次递归都缩小边界，直到越界返回-1。它和循环版本在时间复杂度上完全一致，但在Python默认递归深度约1000的限制下，若数组长度超过这个量级且始终走单边递归，就可能抛出递归错误。
实际工程中，除非问题本身天然具有递归结构，否则更推荐循环写法。如果一定要用递归，可以通过sys.setrecursionlimit提高上限，但这只是权宜之计，不能从根本上消除栈开销。
四、常见错误与边界处理
初学者最容易犯两类错误：一是对未排序列表直接使用二分查找，得到毫无意义的下标；二是中间值计算写成mid = (left + right) / 2却忘了取整，在Python 3中会得到浮点型下标从而报错。另外，当数据量极大时，left + right可能超出整数上限，更稳妥的写法是mid = left + (right - left) // 2。
还有一个隐蔽问题是目标值重复出现时的返回位置。上述基础实现找到任意一个匹配就返回，不保证是第一个或最后一个。如果需要查找左边界或右边界，就要在相等时继续收缩对应侧的区间，这类变体在算法题和数据库索引中十分常见，理解基础版后再扩展并不困难。
| 写法 | 空间复杂度 | 适用场景 |
|---|---|---|
| 循环闭区间 | O(1) | 通用查找、工程代码 |
| 递归闭区间 | O(log n) | 教学演示、递归结构问题 |
五、总结
用Python实现二分查找并不复杂，关键在于严守有序前提与闭区间边界。循环写法以常数空间达成对数时间，是大多数情况下的首选。掌握基础模板后，可进一步练习寻找插入位置、搜索旋转数组等相关题目，从而真正吃透这一基础而强大的算法。
Python二分查找binary_search修改时间：2026-07-31 17:09:26