二分查找也叫折半查找，核心逻辑是每次将查找区间缩小一半，直到找到目标元素或者确定元素不存在，该算法仅适用于元素按升序或降序排列的有序数组，无法在无序数组中直接使用。
二分查找的核心原理
二分查找的执行过程可以分为以下几步：
- 首先确定整个数组的查找区间，左边界为0，右边界为数组长度减1
- 计算区间的中间位置索引，取出中间元素与目标值比较
- 如果中间元素等于目标值，直接返回对应索引
- 如果中间元素小于目标值，说明目标值在右半区间，将左边界更新为中间索引加1
- 如果中间元素大于目标值，说明目标值在左半区间，将右边界更新为中间索引减1
- 重复上述步骤，直到左边界大于右边界，说明目标值不存在，返回-1
迭代方式实现二分查找
迭代实现是最常用的二分查找写法，通过循环不断缩小查找区间，代码逻辑清晰易懂，以下是完整的Python实现代码：
def binary_search_iterative(arr, target):
# 初始化左右边界
left = 0
right = len(arr) - 1
# 当左边界小于等于右边界时，继续查找
while left <= right:
# 计算中间索引，使用(left + right) // 2避免溢出，Python中整数无溢出问题也可直接写
mid = (left + right) // 2
# 找到目标值，返回索引
if arr[mid] == target:
return mid
# 目标值在右半区间，更新左边界
elif arr[mid] < target:
left = mid + 1
# 目标值在左半区间，更新右边界
else:
right = mid - 1
# 循环结束未找到，返回-1
return -1
# 测试代码
if __name__ == "__main__":
test_arr = [1, 3, 5, 7, 9, 11, 13]
target_num = 7
result = binary_search_iterative(test_arr, target_num)
if result != -1:
print(f"找到目标值{target_num}，索引为{result}")
else:
print(f"未找到目标值{target_num}")
递归方式实现二分查找
除了迭代写法，二分查找也可以通过递归实现，递归的实现逻辑和迭代一致，只是把区间更新的操作放到递归调用中，代码如下：
def binary_search_recursive(arr, target, left, right):
# 递归终止条件：左边界大于右边界，未找到目标值
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)
# 测试代码
if __name__ == "__main__":
test_arr = [2, 4, 6, 8, 10, 12]
target_num = 8
result = binary_search_recursive(test_arr, target_num, 0, len(test_arr) - 1)
if result != -1:
print(f"找到目标值{target_num}，索引为{result}")
else:
print(f"未找到目标值{target_num}")
实现时的注意事项
编写二分查找代码时，有几个容易出错的边界问题需要重点关注：
- 中间索引的计算要使用整数除法，避免得到浮点数索引
- 循环条件要根据逻辑选择
left <= right还是left < right，上述两种写法使用的是闭区间，所以循环条件为前者 - 更新左右边界时，要记得加1或者减1，否则可能出现死循环
- 递归实现时要正确设置递归终止条件，避免无限递归
时间复杂度分析
二分查找每次都会将查找区间缩小一半，因此时间复杂度为O(log n)，其中n是数组的长度。相比线性查找的O(n)时间复杂度，二分查找在数组长度较大时优势非常明显。不过二分查找的前提是数组必须有序，如果数组无序，需要先排序再使用二分查找，此时整体时间复杂度会受排序算法影响。
适用场景说明
二分查找适合用在以下场景：
- 数据量较大的有序数组查找
- 需要频繁查找同一有序数组的场景
- 对查找性能要求较高的业务场景
如果数组元素频繁变动，需要不断插入删除元素，维护有序的成本较高，此时不建议使用二分查找，更适合选择其他查找结构。
Python二分查找binary_search修改时间：2026-06-12 21:51:23