二分查找是一种针对有序数据集合的高效查找算法，核心思路是通过不断将查找区间对半分割，缩小目标元素的存在范围，直到找到目标或者确认目标不存在。它的时间复杂度为O(log n)，相比线性查找的O(n)效率提升非常明显，因此被广泛应用于各类查找场景中。
二分查找的基本原理
二分查找的前提是待查找的数组必须是有序的，可以是升序也可以是降序，本文后续示例默认以升序数组为例。查找过程分为以下几个步骤：
- 初始化两个指针，左指针指向数组起始位置，右指针指向数组结束位置
- 计算中间位置mid，对比mid位置的元素和目标值的大小
- 如果mid位置元素等于目标值，直接返回mid索引
- 如果mid位置元素小于目标值，说明目标值在mid右侧，将左指针移动到mid+1的位置
- 如果mid位置元素大于目标值，说明目标值在mid左侧，将右指针移动到mid-1的位置
- 重复上述过程，直到左指针超过右指针，说明目标值不存在，返回-1
二分查找的基础实现示例
以下是升序数组二分查找的基础代码实现，以Python语言为例：
def binary_search(arr, target):
left = 0
right = 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 # 未找到目标值
# 测试示例
test_arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(test_arr, 7)) # 输出3
print(binary_search(test_arr, 8)) # 输出-1
二分查找的核心边界条件
二分查找的边界条件处理是容易出现错误的地方，不同的边界定义对应不同的代码逻辑，下面介绍几个最常见的边界条件相关的问题。
1. 右指针的初始化方式
右指针的初始化有两种常见方式，不同的初始化会影响后续的循环条件和指针移动逻辑：
| 右指针初始化 | 循环条件 | 指针移动规则 | 适用场景 |
|---|---|---|---|
| right = len(arr) - 1 | left <= right | left = mid + 1, right = mid - 1 | 查找目标值的精确索引，区间闭区间[left, right] |
| right = len(arr) | left < right | left = mid + 1, right = mid | 查找第一个大于等于目标值的位置，区间左闭右开[left, right) |
如果右指针初始化为len(arr)，表示查找区间是左闭右开的，此时循环条件需要改为left < right，因为右指针指向的位置本身不在查找范围内，当left等于right时，区间已经为空，不需要继续循环。对应的代码示例如下：
def binary_search_left_open(arr, target):
left = 0
right = len(arr) # 右指针初始化为数组长度，指向的位置不在查找区间内
while left < right: # 循环终止条件：左指针等于右指针，区间为空
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid # 目标值可能在mid位置，右指针移动到mid
return left # 返回第一个大于等于target的位置
test_arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search_left_open(test_arr, 7)) # 输出3
print(binary_search_left_open(test_arr, 8)) # 输出4，即第一个大于8的元素9的位置
2. 循环终止条件
循环终止条件需要和右指针的初始化方式匹配，常见的错误是混用两种边界定义的逻辑，比如右指针初始化为len(arr)-1却使用left < right作为循环条件，这会导致当目标值刚好在最后一个元素时无法被查找到。
当使用闭区间[left, right]时，循环条件必须是left <= right，因为当left等于right时，区间仍然包含一个元素，需要继续判断；当使用左闭右开区间[left, right)时，循环条件必须是left < right，因为left等于right时区间已经没有元素了。
3. mid的计算方式
计算mid时如果使用(left + right) // 2，在left和right都很大的时候可能会出现整数溢出的问题，不过在Python中整数没有大小限制，这个问题不常见，但在Java、C++等语言中需要注意，可以使用left + (right - left) // 2的方式计算mid，避免溢出。
另外，在查找第一个等于目标值或者最后一个等于目标值的位置时，mid的计算可能需要向上取整，避免死循环。比如查找第一个大于等于目标值的位置时，如果mid计算向下取整，当区间只剩两个元素且left指向的元素小于target，right指向的元素大于等于target时，mid会一直等于left，导致left永远无法更新，进入死循环。此时可以将mid的计算改为(left + right + 1) // 2，向上取整。
4. 指针移动的规则
指针移动的规则也需要和区间定义匹配，闭区间场景下，当arr[mid]不等于target时，target肯定不在mid位置，因此left可以移动到mid+1，right可以移动到mid-1；而左闭右开区间场景下，当arr[mid]大于等于target时，target可能在mid位置，因此right只能移动到mid，不能移动到mid-1，否则会漏掉mid位置的元素。
常见边界错误案例
以下是一个典型的边界错误示例，右指针初始化为len(arr)-1，却使用了左闭右开的指针移动逻辑：
def wrong_binary_search(arr, target):
left = 0
right = 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 # 错误：闭区间下right应该移动到mid-1
return -1
test_arr = [1, 3, 5, 7, 9]
print(wrong_binary_search(test_arr, 9)) # 会进入死循环
上述代码中，当查找目标值为9时，left=0，right=4，mid=2，arr[2]=5<9，left变为3；此时mid=(3+4)//2=3，arr[3]=7<9，left变为4；此时mid=(4+4)//2=4，arr[4]=9等于target，返回4，看似没有问题，但如果目标值不存在，比如查找10，left=4，right=4，mid=4，arr[4]=9<10，left变为5，此时left>right，循环结束返回-1，这个场景下不会出错，但如果数组是[1,3,5,7,9,10]，查找10，也会出现类似的问题吗？其实这个例子的错误更典型的是当arr[mid]大于target时，right移动到mid，会导致当区间只剩两个元素时，right永远无法小于left，比如数组[1,2]，查找0，left=0，right=1，mid=0，arr[0]=1>0，right变为0，此时left=0，right=0，mid=0，arr[0]还是大于0，right又变为0，进入死循环。
总结
二分查找的边界条件处理核心是保持区间定义的一致性，无论是选择闭区间还是左闭右开区间，后续的循环条件、指针移动规则都要和初始的区间定义匹配，不能随意混用。在编写二分查找代码时，可以先明确自己的区间定义，再按照对应的逻辑编写代码，这样可以有效避免大部分边界错误。如果遇到复杂的二分查找场景，比如查找第一个等于目标值的位置、查找最后一个等于目标值的位置，也可以先明确区间定义，再调整对应的逻辑，确保代码的正确性。
二分查找binary_search算法边界条件修改时间：2026-07-11 09:54:36