一、算法概述

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法，时间复杂度为 O(log n)。二分答案（Binary Search Answer）是基于二分思想解决最优化问题的技巧，常用于"最小化最大值"或"最大化最小值"类型的问题。

二、二分查找核心模板

2.1 标准闭区间写法

def binary_search_standard(nums, target):
    """
    在有序数组nums中查找target
    返回target的索引，如果不存在则返回-1
    """
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    
    while left <= right:  # 区间不为空时继续搜索
        # 防止整数溢出
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid  # 找到目标，返回索引
        elif nums[mid] < target:
            left = mid + 1  # 目标在右半部分
        else:
            right = mid - 1  # 目标在左半部分
    
    return -1  # 未找到目标

# 测试示例
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search_standard(arr, target)
print(f"在数组{arr}中查找{target}，结果索引：{result}")

模板解析：

• 使用闭区间 [left, right]

• 循环条件：left <= right

• 中点计算：mid = left + (right - left) // 2（防溢出）

• 返回找到的索引或-1

2.2 查找左侧边界

def binary_search_left(nums, target):
    """
    查找第一个等于target的位置（左边界）
    如果target不存在，返回-1
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    
    # 检查left是否越界且是否等于target
    if left < len(nums) and nums[left] == target:
        return left
    return -1

2.3 查找右侧边界

def binary_search_right(nums, target):
    """
    查找最后一个等于target的位置（右边界）
    如果target不存在，返回-1
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    
    # 检查right是否越界且是否等于target
    if right >= 0 and nums[right] == target:
        return right
    return -1

三、递归与非递归实现对比

3.1 递归实现

def binary_search_recursive(alist, item):
    """
    递归实现二分查找
    优点：代码简洁，易于理解
    缺点：空间复杂度高，效率较低
    """
    if len(alist) == 0:
        return False
    
    midpoint = len(alist) // 2
    
    if alist[midpoint] == item:
        return True
    elif item < alist[midpoint]:
        return binary_search_recursive(alist[:midpoint], item)
    else:
        return binary_search_recursive(alist[midpoint + 1:], item)

# 测试递归版本
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(f"递归查找3：{binary_search_recursive(testlist, 3)}")
print(f"递归查找13：{binary_search_recursive(testlist, 13)}")

3.2 非递归实现（推荐）

def binary_search_iterative(alist, item):
    """
    非递归实现二分查找
    优点：空间复杂度低，效率高
    缺点：代码稍复杂
    """
    first = 0
    last = len(alist) - 1
    
    while first <= last:
        midpoint = (first + last) // 2
        
        if alist[midpoint] == item:
            return True
        elif item < alist[midpoint]:
            last = midpoint - 1
        else:
            first = midpoint + 1
    
    return False

# 测试非递归版本
print(f"非递归查找3：{binary_search_iterative(testlist, 3)}")
print(f"非递归查找13：{binary_search_iterative(testlist, 13)}")

四、二分查找例题详解

例1：有序序列中查找元素

问题描述：在一个有序数组 nums 中查找多个数字 figure 的第一次出现的位置（1-based索引），如果找不到则返回 -1。

# 读取输入：n 是数组长度，m 是要查询的数字个数
n, m = map(int, input().split())

# 读取有序数组 nums
nums = list(map(int, input().split()))

# 读取要查询的数字列表 figure
figure = list(map(int, input().split()))

# 存储查询结果
res = []

# 对每个要查询的数字 f 进行二分查找
for f in figure:
    # 二分查找的左右边界（0-based索引）
    left, right = 0, n - 1
    ans = -1  # 默认值为 -1（表示未找到）
    
    # 标准的二分查找模板
    while left <= right:
        mid = (left + right) // 2  # 计算中间位置
        
        if nums[mid] == f:
            # 找到目标值
            ans = mid + 1  # 转换为 1-based 索引（题目要求）
            # 为了找到第一次出现的位置，继续向左搜索
            right = mid - 1
        elif nums[mid] < f:
            # 中间值小于目标值，说明目标在右侧
            left = mid + 1
        else:
            # 中间值大于目标值，说明目标在左侧
            right = mid - 1
    
    # 将结果转换为字符串添加到结果列表
    res.append(str(ans))

# 输出结果，用空格分隔
print(' '.join(res))

例2：A-B数对问题

问题描述：在一个有序数组中，统计有多少对数字 (b, a) 满足 a - b = c，即统计数组中相差为 c 的数对数量。

# 查找目标值 a 在有序数组 arr 中第一次出现的位置（左边界）
def find_left(arr, a, left, right):
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] >= a:  # 如果中间值大于等于目标值
            right = mid - 1  # 向左搜索，寻找第一次出现的位置
        else:
            left = mid + 1  # 向右搜索
    return left  # 返回左边界索引

# 查找目标值 a 在有序数组 arr 中最后一次出现的位置（右边界）
def find_right(arr, a, left, right):
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] > a:  # 如果中间值大于目标值
            right = mid - 1  # 向左搜索
        else:
            left = mid + 1  # 向右搜索，寻找最后一次出现的位置
    return right  # 返回右边界索引

# 主程序开始
n, c = map(int, input().split())  # n是数组长度，c是目标差值
s = list(map(int, input().split()))  # 读取数组
s.sort()  # 排序数组，方便二分查找

count = 0  # 统计满足条件的数对数量

# 遍历数组中的每个数字 b
for i in range(n):
    b = s[i]  # 当前数字 b
    a = b + c  # 需要寻找的对应数字 a = b + c
    
    # 查找 a 第一次出现的位置
    left_idx = find_left(s, a, 0, n - 1)
    
    # 检查是否找到了 a
    if left_idx < n and s[left_idx] == a:
        # 如果找到了，继续查找 a 最后一次出现的位置
        right_idx = find_right(s, a, 0, n - 1)
        # 计算 a 出现的次数，并加到总数中
        count += (right_idx - left_idx + 1)

print(count)

五、二分答案算法详解

二分答案是一种应用二分查找思想解决优化问题的技巧，通常包含三个步骤：

1. 确定答案的搜索范围

2. 设计检查函数，判断某个答案是否可行

3. 二分搜索寻找最优解

5.1 整数二分答案模板

def binary_answer_max(check_func, left, right):
    """
    寻找最大的可行解（最大化最小值问题）
    check_func: 检查函数，接收一个参数，返回是否可行
    """
    ans = left
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if check_func(mid):
            ans = mid  # 当前mid可行，尝试更大的
            left = mid + 1
        else:
            right = mid - 1  # 当前mid不可行，减小
    
    return ans

def binary_answer_min(check_func, left, right):
    """
    寻找最小的可行解（最小化最大值问题）
    """
    ans = right
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if check_func(mid):
            ans = mid  # 当前mid可行，尝试更小的
            right = mid - 1
        else:
            left = mid + 1  # 当前mid不可行，增大
    
    return ans

5.2 浮点数二分答案模板

def binary_answer_float(check_func, left, right, precision=1e-6):
    """
    浮点数二分答案
    precision: 精度要求
    """
    while right - left > precision:
        mid = (left + right) / 2
        
        if check_func(mid):
            # 根据问题类型决定保留哪一半
            # 对于最大化问题：保留右半部分
            left = mid
        else:
            right = mid
    
    return (left + right) / 2

六、二分答案例题详解

例3：砍树问题（木材收集）

问题描述：将一系列树木切割到同一高度，使得得到的木材总长度至少为 m，求最大的切割高度。

# 输入：n 是树木数量，m 是需要获得的最少木材长度
n, m = map(int, input().split())

# 读取每棵树的高度
tember = list(map(int, input().split()))

# 二分查找的初始边界
# low: 最低切割高度（可以是 0，表示砍到地面）
# high: 最高切割高度（即最高树的高度，表示不砍任何树）
low, high = 0, max(tember)

num = 0  # 记录当前找到的满足条件的最佳高度

# 函数：计算如果将树切割到高度 h 时能获得的木材总量
def get_wood(h):
    total = 0
    for tree in tember:
        if tree > h:  # 只有高于 h 的树才能被砍
            total += tree - h  # 砍下的木材长度
    return total

# 二分查找：寻找最大的切割高度 h，使得 get_wood(h) >= m
while low <= high:
    mid = (low + high) // 2  # 尝试的切割高度
    wood = get_wood(mid)     # 计算在当前高度下能获得的木材
    
    if wood >= m:
        # 如果获得的木材足够或超过需求，说明切割高度 mid 可行
        # 但可能可以切得更高（mid 更大，得到更少的木材但仍然 >= m）
        num = mid    # 更新最佳高度
        low = mid + 1  # 尝试更大的高度
    else:
        # 木材不足，说明切得太高了，需要降低切割高度
        high = mid - 1

# 输出最大可行高度
print(num)

例4：进击的奶牛（最大化最小距离）

def max_min_distance(stalls, C):
    """
    N个牛棚位置在stalls，要放入C头牛
    最大化两头牛之间的最小距离
    """
    stalls.sort()  # 先排序
    
    def check(distance):
        """检查最小距离distance是否可行"""
        count = 1  # 第一头牛放在第一个牛棚
        last_pos = stalls[0]
        
        for i in range(1, len(stalls)):
            if stalls[i] - last_pos >= distance:
                count += 1
                last_pos = stalls[i]
                if count >= C:  # 已放置足够多的牛
                    return True
        return False
    
    # 最小距离范围：0到最大间隔
    left, right = 0, stalls[-1] - stalls[0]
    
    # 寻找最大的可行距离
    return binary_answer_max(check, left, right)

# 测试进击的奶牛
stalls = [1, 2, 4, 8, 9]
C = 3
result = max_min_distance(stalls, C)
print(f"牛棚位置{stalls}，放入{C}头牛，最大化的最小距离：{result}")

例5：一元三次方程求解

问题描述：解一元三次方程 ax3+bx2+cx+d=0ax3+bx2+cx+d=0 的所有实数根，并保留两位小数输出。

# 输入三次方程的系数 a, b, c, d
a, b, c, d = map(float, input().split())

# 定义三次函数 f(x)
def f(a, b, c, d, x):
    return a * (x ** 3) + b * (x ** 2) + c * x + d

roots = []  # 存储找到的根
eps = 1e-8  # 用于判断浮点数是否为0的小量

# 遍历区间 [-100, 100]，每个长度为1的子区间
for left in range(-100, 100):
    right = left + 1
    y1 = f(a, b, c, d, left)
    y2 = f(a, b, c, d, right)
    
    # 情况1：左端点恰好是根
    if abs(y1) < eps:
        root_rounded = round(left, 2)  # 四舍五入保留两位
        # 去重检查：避免重复添加相同的根
        if not any(abs(root_rounded - r) < 0.001 for r in roots):
            roots.append(root_rounded)
    
    # 情况2：函数值在区间两端异号，说明区间内有根
    elif y1 * y2 < 0:
        l, r = left, right
        # 二分法精确求根
        while r - l > eps:
            mid = (l + r) / 2
            # 如果 mid 与左端点函数值同号，根在右半区间
            if f(a, b, c, d, mid) * f(a, b, c, d, l) > 0:
                l = mid
            else:
                r = mid
        root = (l + r) / 2  # 取中间作为根的近似值
        root_rounded = round(root, 2)  # 保留两位
        # 去重
        if not any(abs(root_rounded - r) < 0.001 for r in roots):
            roots.append(root_rounded)

# 特殊检查右端点 x = 100 是否为根
if abs(f(a, b, c, d, 100)) < eps:
    if not any(abs(100.00 - r) < 0.001 for r in roots):
        roots.append(100.00)

# 排序并输出结果
roots.sort()
print(' '.join(f'{r:.2f}' for r in roots))

七、算法对比与选择指南

特性	二分查找	二分答案
应用场景	有序数组中查找元素	优化问题的最值求解
输入要求	有序序列	答案具有单调性
核心函数	直接比较元素值	需要构造检查函数
返回值	元素索引或是否存在	最优解的值
时间复杂度	O(log n)	O(log R * f(n))，R为答案范围

八、实战技巧与注意事项

8.1 边界条件处理

# 处理空数组
def safe_binary_search(nums, target):
    if not nums:  # 空数组
        return -1
    return binary_search_standard(nums, target)

# 处理单个元素数组
def test_edge_cases():
    test_cases = [
        ([], 5),          # 空数组
        ([1], 1),         # 单个元素，找到
        ([1], 2),         # 单个元素，未找到
        ([1, 3], 2),      # 两个元素，未找到
        ([1, 3], 3),      # 两个元素，找到
    ]
    
    for nums, target in test_cases:
        result = safe_binary_search(nums, target)
        print(f"在{nums}中查找{target}: {result}")

8.2 防溢出技巧

# 错误的写法（可能溢出）
mid = (left + right) // 2

# 正确的写法（防溢出）
mid = left + (right - left) // 2

# 对于极大数据，可以使用位运算
mid = (left + right) >> 1  # 右移一位相当于除以2

8.3 调试技巧

def debug_binary_search(nums, target):
    """
    带有调试信息的二分查找
    """
    left, right = 0, len(nums) - 1
    step = 0
    
    print(f"开始查找 {target}")
    print(f"初始区间: [{left}, {right}]")
    
    while left <= right:
        step += 1
        mid = left + (right - left) // 2
        print(f"步骤{step}: left={left}, right={right}, mid={mid}, nums[mid]={nums[mid]}")
        
        if nums[mid] == target:
            print(f"找到目标，索引={mid}")
            return mid
        elif nums[mid] < target:
            left = mid + 1
            print(f"目标在右侧，新区间: [{left}, {right}]")
        else:
            right = mid - 1
            print(f"目标在左侧，新区间: [{left}, {right}]")
    
    print(f"未找到目标，总步骤数={step}")
    return -1

九、总结

二分查找与二分答案是算法竞赛和实际编程中极其重要的技巧。通过本文的学习，应该掌握：

1. 二分查找的基本原理：在有序序列中高效查找元素

2. 各种模板的实现：闭区间、开区间、递归与非递归

3. 边界查找技巧：查找第一个、最后一个、左边界、右边界

4. 二分答案的应用：解决最优化问题

5. 实战技巧：防溢出、边界处理、调试方法

关键要点：

• 理解循环不变量，确保算法正确性

• 根据问题选择合适的模板

• 注意边界条件和特殊情况的处理

• 对于二分答案问题，设计高效的检查函数

（本文例题源于洛谷）