蓝桥杯python备赛笔记之（五）二分查找 & 二分答案

import bisect
# 语法：bisect.bisect(a, x, lo=0, hi=len(a))
# a：单调不减的数组
# x：待查找的目标值
# lo/hi：查找区间[lo, hi)，左闭右开，默认整个数组
# 返回值：第一个严格大于x的下标位置
a = [1, 9, 9, 9, 200, 500]
print(bisect.bisect(a, 9))  # 输出4：第一个大于9的数是200，下标为4
print(bisect.bisect(a, 100)) # 输出4：100小于200，第一个大于100的下标为4

1.1.2 常见变形（必考）

bisect 仅提供严格大于 x的基础功能，蓝桥杯常考大于等于、小于等于、小于等变形，通过简单推导即可实现，整理为速记公式如下（均基于单调不减数组）：

查找目标	计算公式	示例（a=[1,9,9,9,200,500]）
第一个严格大于 x	bisect.bisect(a, x)	bisect(a,9)=4
第一个大于等于 x	bisect.bisect(a, x-1)	bisect (a,8)=1（第一个≥9 的下标 1）
最后一个小于等于 x	bisect.bisect(a, x) - 1	bisect (a,9)-1=3（最后一个≤9 的下标 3）
最后一个小于 x	bisect.bisect(a, x-1) - 1	bisect (a,9)-1=0（最后一个 < 9 的下标 0）

1.1.3 单调不增数组的处理

若数组为单调不增，先将数组取反转为单调不减，再用 bisect 计算，最后映射回原数组下标：

import bisect
a = [500, 200, 9, 9, 9, 1]  # 单调不增
x = 9
# 取反得到单调不减数组
a_rev = [-num for num in a]
x_rev = -x
# 查找原数组中第一个小于x的下标
pos = bisect.bisect(a_rev, x_rev)
print(pos)  # 输出5：原数组中第一个小于9的数是1，下标5

1.2 朴素二分（自定义 check，核心重点）

内置bisect的局限性：Python3.8 及以下版本不支持传递自定义校验函数，而蓝桥杯部分竞赛环境为低版本，且很多题型需要自定义查找条件（如查找满足a[i]^3 + a[i]^2 > 1000的第一个位置）。

此时需要实现朴素二分，核心是基于自定义 check 函数的区间更新，适配所有二分查找场景。

1.2.1 实现思路

定义查找区间为左闭右开 [lo, hi)，初始lo=0，hi=len(a)；
计算中点i = (lo + hi) >> 1（位运算替代整除，速度更快，蓝桥杯优化必备）；
根据check(a[i])的结果更新区间：
- 若check(a[i]) > x：目标在左半区，更新hi = i；
- 否则：目标在右半区，更新lo = i + 1；
循环至lo == hi，此时lo（或hi）即为目标下标。

1.2.2 通用模板（支持自定义 check）

def bisect_custom(a, x, lo=0, hi=None, check=lambda y: y):
    """
    自定义二分查找，支持任意校验条件
    :param a: 单调不减数组
    :param x: 目标值
    :param lo/hi: 查找区间[lo, hi)
    :param check: 校验函数，默认返回元素本身（等价于内置bisect）
    :return: 第一个使check(a[i]) > x的下标
    """
    if hi is None:
        hi = len(a)
    while lo < hi:
        i = (lo + hi) >> 1  # 中点，整数向下取整
        if check(a[i]) > x:
            hi = i
        else:
            lo = i + 1
    return lo

# 示例：查找满足y^3 + y^2 + 1 > 1000的第一个位置
a = [1, 9, 9, 9, 200, 500]
x = 1000
# 自定义check函数
check_fun = lambda y: y**3 + y**2 + 1
pos = bisect_custom(a, x, check=check_fun)
print(pos)  # 输出4：a[4]=200，满足200^3+200^2+1>>1000

1.2.3 模板适配基础变形

将check函数设为默认的lambda y:y，即可实现内置 bisect 的所有变形，与 1.1.2 的速记公式完全一致。

二、二分答案（蓝桥杯大题核心，重中之重）

二分答案并非直接查找某个值，而是将 “求最值问题” 转化为 “判定问题”，是蓝桥杯中等难度大题的必考技巧，常考题型：分巧克力、数的范围、木材切割、最大公约数相关最值等。

2.1 核心适用条件（三大条件，缺一不可）

求最值：题目要求最大值 / 最小值 / 最优解（如 “最大的正方形边长”“最小的分割数”）；
答案有界：答案res存在一个确定、连续的整数区间 [lo, hi]（可通过题目条件快速确定）；
可快速校验：对任意候选答案mid，能通过check(mid) 快速判断其是否满足题目条件（check 函数的时间复杂度越低越好，通常为 O (n)）。

2.2 解题核心：答案的单调性

二分答案的本质是利用答案的单调性找临界点，蓝桥杯最常见的是 **「不满足→满足」的单调递增临界点 **：

当候选答案mid小于最优解时，check(mid) = True（满足条件）；
当候选答案mid大于最优解时，check(mid) = False（不满足条件）；
临界点即为满足条件的最大 / 最小答案。

2.3 标准解题步骤（四步走，无脑套用）

确定答案区间：根据题目条件定初始lo（答案最小值）和hi（答案最大值）；
编写 check 函数：输入候选答案mid，返回True/False表示是否满足条件（核心步骤）；
二分查找临界点：在 [lo, hi] 上执行二分，根据 check 结果更新区间；
输出答案：循环结束后，lo/hi即为最优解。

2.4 通用模板（整数二分答案，蓝桥杯通用）

def binary_answer():
    # 步骤1：确定答案的初始区间[lo, hi]
    lo = 最小值（如1）
    hi = 最大值（如10**9，根据题目定）
    ans = 0  # 存储最优解
    while lo <= hi:  # 二分答案常用闭区间[lo, hi]，与二分查找区分
        mid = (lo + hi) >> 1
        # 步骤2：执行check校验
        if check(mid):
            # 满足条件，尝试找更优的解（求最大则右移，求最小则左移）
            ans = mid
            lo = mid + 1  # 求最大值时用，若求最小值则hi=mid-1
        else:
            # 不满足条件，缩小范围
            hi = mid - 1  # 求最大值时用，若求最小值则lo=mid+1
    return ans

# 步骤2：编写check函数（根据题目自定义，示例为占位）
def check(mid):
    # 逻辑：判断mid是否满足题目条件
    flag = True
    # ... 题目具体逻辑
    return flag

关键区分：二分答案常用闭区间 [lo, hi]，而二分查找常用左闭右开 [lo, hi)，避免边界出错。

三、蓝桥杯高频杂项补充

笔记中提及的Counter和自定义 Set是二分题型的辅助工具，常用来做计数、去重，蓝桥杯中频繁出现，在此整理为实用模板。

3.1 Counter：快速计数 + 取高频元素

collections.Counter是 Python 内置的计数工具，替代手动写字典计数，效率更高，适合统计数组 / 列表中元素的出现次数。

from collections import Counter

# 1. 基础计数
lst = ["a", "a", "a", "b", "c", "g", "g", "g"]
cnt = Counter(lst)
print(cnt)  # 输出：Counter({'a': 3, 'g': 3, 'b': 1, 'c': 1})

# 2. 取前k个高频元素（most_common(k)）
top3 = cnt.most_common(3)
print(top3)  # 输出：[('a', 3), ('g', 3), ('b', 1)]
top1 = cnt.most_common(1)[0][0]  # 取出现次数最多的元素
print(top1)  # 输出：a

# 3. 访问元素出现次数
print(cnt.get("a", 0))  # 输出3，不存在则返回0（避免KeyError）

3.2 自定义 Set：个性化去重

Python 内置set仅支持基础去重，蓝桥杯常考“排列无关的去重”（如 (1,2,1) 和 (2,1,1) 视为同一个元素），需自定义 Set 重写add方法。

class MySet(set):
    def add(self, element):
        # 将元素排序后转元组，实现排列无关的去重
        sorted_ele = tuple(sorted(element))
        # 检查是否已存在，不存在则调用父类add方法
        if not any(sorted_ele == e for e in self):
            super().add(sorted_ele)

# 示例：对元组排列去重
s = MySet()
s.add((2, 1, 1))
s.add((1, 2, 1))
s.add((3, 2))
print(s)  # 输出：{(1, 1, 2), (2, 3)}

四、蓝桥杯经典例题（二分查找 + 二分答案）

例题 1：二分查找 —— 找目标值的第一个出现位置（填空题）

题目：给定单调不减数组a = [1,3,5,5,5,7,9]，找到目标值 5 的第一个出现位置（答案：2）。解题思路：用 bisect 的大于等于 x变形，直接套用公式。

import bisect
a = [1,3,5,5,5,7,9]
x = 5
# 第一个大于等于x的下标 = bisect.bisect(a, x-1)
pos = bisect.bisect(a, x-1)
print(pos)  # 输出2

例题 2：二分答案 —— 分巧克力（蓝桥杯经典大题）

题目：儿童节有 n 块巧克力，每块巧克力是 h×w 的矩形，要求将所有巧克力切成大小相同的正方形，且正方形边长为整数，问最大的正方形边长是多少？输入：第一行 n（巧克力数），接下来 n 行每行 h,w；输出：最大正方形边长。解题思路：

答案区间：边长最小 1，最大为所有巧克力的最大边长（max (h1,w1,h2,w2,...)）；
check 函数：判断边长为 mid 时，所有巧克力能切出的正方形总数≥n（实际题目常要求切出 k 块，此处简化为 n）；
二分找满足条件的最大 mid。

代码实现：

def check(mid, chocolate):
    """判断边长mid是否满足条件：能切出足够的正方形"""
    total = 0
    for h, w in chocolate:
        total += (h // mid) * (w // mid)
        if total >= len(chocolate):  # 提前终止，优化速度
            return True
    return total >= len(chocolate)

def binary_answer_chocolate():
    # 输入处理（蓝桥杯标准输入）
    import sys
    input = sys.stdin.readline
    n = int(input())
    chocolate = []
    max_len = 0
    for _ in range(n):
        h, w = map(int, input().split())
        chocolate.append((h, w))
        max_len = max(max_len, h, w)
    # 步骤1：确定答案区间
    lo = 1
    hi = max_len
    ans = 0
    # 步骤3：二分查找
    while lo <= hi:
        mid = (lo + hi) >> 1
        if check(mid, chocolate):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

# 测试
print(binary_answer_chocolate())
# 输入示例：
# 3
# 6 8
# 5 5
# 7 9
# 输出：3

五、蓝桥杯二分易错点总结（避坑必备）

区间定义混乱：二分查找用左闭右开 [lo, hi)，二分答案用闭区间 [lo, hi]，不要混用；
中点计算：用(lo + hi) >> 1替代(lo + hi) // 2，速度更快，且整数域结果一致；
bisect 的左闭右开：bisect 的 hi 参数是开区间，如bisect(a, x, 0, 3)仅查找数组前 3 个元素（下标 0,1,2）；
check 函数编写：二分答案的核心是 check 函数，需严格根据题目条件编写，注意提前终止（如分巧克力中 total≥n 时直接返回 True），优化时间复杂度；
答案区间的边界：hi 不要设得太小（如直接设 10^9，Python 整数无溢出，不影响效率），避免漏解；
单调数组的确认：使用 bisect 前必须确保数组单调不减，否则结果错误。