03_二分查找

二分查找

模板

有序数组：bisect

bisect 函数	对应 C++	含义
bisect.bisect_left(arr, x)	lower_bound	第一个 >= x 的下标
bisect.bisect_right(arr, x)	upper_bound	第一个 > x 的下标

import bisect

arr = sorted([...])  # 先排序

# lower_bound: 第一个 >= x 的位置
pos = bisect.bisect_left(arr, x)

# upper_bound: 第一个 > x 的位置
pos = bisect.bisect_right(arr, x)

常用派生技巧：

x 的个数          = bisect_right(arr, x) - bisect_left(arr, x)
<= x 的个数       = bisect_right(arr, x)
<  x 的个数       = bisect_left(arr, x)
值域 [l, r] 内个数 = bisect_right(arr, r) - bisect_left(arr, l)
等于 x 的下标区间  = [bisect_left(arr, x), bisect_right(arr, x))

单调函数：max_ok / min_ok

模式	函数	功能	无解时返回
找最大可行值	max_ok(lo, hi, check)	找最大的 x 使得 check(x)=True	lo - 1
找最小可行值	min_ok(lo, hi, check)	找最小的 x 使得 check(x)=True	hi + 1

from typing import Callable

def max_ok(lo: int, hi: int, check: Callable[[int], bool]) -> int:
    """查找最大的 x 使得 check(x) = True"""
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def min_ok(lo: int, hi: int, check: Callable[[int], bool]) -> int:
    """查找最小的 x 使得 check(x) = True"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2  # 向下取整
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

解释

二分搜索的核心思想是利用单调性快速缩小搜索区间

用途：$O(\log n)$ 定位目标——有序数组上找位置 / 单调判定函数上找边界。

原理：每次与区间中点比较，把搜索范围缩小一半。

手写二分查找

# 查找左边界（第一个 >= target 的位置）
def lower_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 查找右边界（第一个 > target 的位置）
def upper_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

单调函数的概念

当我们需要在单调函数上二分时，搜索对象是一个布尔函数 check(x)，满足单调性：

• 如果 check(x) = True，则 check(y) = True 对所有 y ≤ x（或 y ≥ x）

max_ok 适用的条件： - 如果 check(x) = True，则对所有 y ≤ x 都有 check(y) = True - 如果 check(x) = False，则对所有 y ≥ x 都有 f(y) = false

min_ok 适用的条件： - 如果 check(x) = True，则对所有 y ≥ x 都有 check(y) = True - 如果 check(x) = False，则对所有 y ≤ x 都有 f(y) = false

例如，对于以下函数：

check(1) = True, check(2) = True, check(3) = True, check(4) = True, check(5) = True
check(6) = False, check(7) = False, check(8) = False

则 max_ok(1, 8, check) = 5，min_ok(1, 8, check) = 1。

常见错误

错误 1：mid 取整方向错误。当 lo = 0, hi = 1 时，如果使用向下取整：

mid = (lo + hi) // 2  # = 0，会导致无限循环

修复：根据搜索方向选择正确的取整方式——找最大可行值（向右收缩）→ 向上取整 (hi - lo + 1) // 2；找最小可行值（向左收缩）→ 向下取整 (hi - lo) // 2。

错误 2：负数边界。mid = (lo + hi) // 2 对负数会向上取整！修复：

mid = lo + (hi - lo) // 2

例题

例题 1：Counting Haybales

来源：USACO - Haybales

给定 N 个不同位置的干草捆，有 Q 次查询，每次查询区间 [A, B] 内有多少个干草捆。

• N, Q ≤ 100,000
• 坐标范围：0 ~ 1,000,000,000

思路： 1. 先将所有干草捆位置排序 2. 对于每次查询 [A, B]： - <= B 的个数：upper_bound(B) - <= A-1 的个数：upper_bound(A-1) - 答案 = upper_bound(B) - upper_bound(A-1)

import sys
from bisect import bisect_right
sys.stdin = open("haybales.in", "r")
sys.stdout = open("haybales.out", "w")

N, Q = map(int, input().split())
arr = sorted(list(map(int, input().split())))

for _ in range(Q):
    a, b = map(int, input().split())
    print(bisect_right(arr, b) - bisect_right(arr, a - 1))

复杂度：O(N log N + Q log N)

例题 2：最大中位数（单调函数 + max_ok）

来源：Codeforces - Maximum Median

给定 n 个整数的数组（n 为奇数），可以进行 k 次操作（每次+1），求最大可达中位数。

1 ≤ n ≤ 2 × 10^5，1 ≤ k ≤ 10^9

思路：

1. 排序数组：先对数组进行升序排序

2. 观察：要将中位数提升到 x，需要将所有大于等于当前中位数的元素都提升到至少 x

   例如，对于排序后的数组 [1,1,2,3,4,4,5,5,6,8,8]，当前中位数是 4，要将中位数提升到 6，需要：

   • 将 4 → 6（2 次操作）
   • 将 5 → 6（1 次操作 × 2 个）
   • 将 6,8,8 保持不变

3. 单调性：将中位数提升到 x 所需的操作数随着 x 增加而单调递增

4. 二分搜索：使用 max_ok 找到最大的 x 使得所需操作数 ≤ k

n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
arr.sort()

def max_ok(lo, hi, check):
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def med_reachable(x):
    ops = 0
    for i in range((n - 1) // 2, n):
        ops += max(0, x - arr[i])
    return ops <= k

ans = max_ok(1, int(2e9), med_reachable)
print(ans)

例题 3：Cow Dance Show（min_ok + 堆模拟）

来源：USACO - Cow Dance Show

有 N 头牛按顺序表演，每头牛舞蹈时长为 d(i)。舞台能容纳 K 头牛同时表演。初始时前 K 头牛上台，当其中任何一头牛完成表演后，立即由下一头牛补上（直到所有牛表演完）。求在演出时间不超过 Tmax 的前提下，最小的 K 是多少。

1 ≤ N ≤ 10,000，Tmax ≤ 10^6，1 ≤ d(i) ≤ 100,000

思路：

1. 单调性：K 越大，演出时间 T 越小

   • 如果 K 可以让演出在 Tmax 内完成，那么 K+1、K+2 也可以
   • 单调递增：随着 K 增大，T 单调递减

2. 二分搜索：使用 min_ok 找到最小的可行 K

3. 模拟演出：使用小顶堆模拟 K 个同时在舞台上的牛

   • 每次取出最早结束的牛，用下一头牛替换
   • 最终演出时间 = 堆中所有牛完成时间的最大值

import sys
import heapq

sys.stdin = open("cowdance.in", "r")
sys.stdout = open("cowdance.out", "w")

n, t = map(int, input().split())
d = [int(input()) for _ in range(n)]

def fun(k):
    """模拟舞台大小为 k 时的演出时间"""
    show = d[:k]
    heapq.heapify(show)
    for i in range(k, n):
        earliest = heapq.heappop(show)  # 最早结束的牛
        heapq.heappush(show, earliest + d[i])  # 下一头牛上台
    return max(show)  # 最终演出时间

def min_ok(lo, hi, check):
    """查找最小的 x 使得 check(x) = True"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_ok(1, n, lambda k: fun(k) <= t))

关键点： - 搜索范围：[1, N]（最多 N 头牛同时上台） - 单调性：K 越大 T 越小 → 使用 min_ok 找最小可行 K - 堆的作用：O(N log K) 时间模拟演出过程

例题 4：Convention 机场接机（min_ok + 贪心验证）

来源：USACO - Convention

有 N 头奶牛到达机场，时间为 t1…tN。有 M 辆大巴，每辆可乘 C 头奶牛。大巴发车时间 = 最后一头乘坐该大巴的奶牛的到达时间。求最大等待时间（发车时间 - 到达时间）的最小值。

N, M ≤ 10^5，C ≤ N，ti ≤ 10^9

思路：

1. 排序：将奶牛到达时间按升序排列

2. 问题转化：不直接问”能否用 M 辆大巴在等待时间 X 内完成”，而是问”在等待时间 X 内最少需要多少辆大巴”

3. 单调性：

   • 如果在等待时间 X 下无法完成，那么更小的 X 也不可能完成
   • 随着 X 增大，所需大巴数单调递减

4. 验证函数的三种情况（处理每头牛）：

   • 添加这头牛会导致第一头牛超过最大等待时间 → 开新大巴
   • 添加这头牛会导致大巴超载 → 开新大巴
   • 可以加入当前大巴 → 直接加入

5. 二分搜索：使用 min_ok 找到最小的可行 X

def can_arrange(x):
    """检查是否能在最大等待时间 x 内用 M 辆大巴接完所有奶牛"""
    need_bus = 1          # 第一辆大巴
    first_ind = 0         # 当前大巴上第一头牛的索引
    cow_up = 1            # 当前大巴上的牛数量

    for i in range(1, n):
        # 等待时间超限或容量满，新开大巴
        if time[i] - time[first_ind] > x or cow_up == c:
            first_ind = i
            need_bus += 1
            cow_up = 1
        else:
            cow_up += 1

    return need_bus <= m

def min_ok(lo, hi, check):
    """查找最小的 x 使得 check(x) = True"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

n, m, c = map(int, input().split())
time = sorted([int(x) for x in input().split()])

ans = min_ok(0, time[-1] - time[0], can_arrange)
print(ans)

关键点： - 搜索范围：[0, max_time - min_time] - 单调性：X 越大，所需大巴数越少 → 使用 min_ok - 复杂度：O(N log N)