Binary Search 二分搜索

什么是二分搜索？

二分搜索是一种在有序数组中查找目标值的高效算法，时间复杂度为 O(log n)。

基本思想

每次将搜索区间缩小一半，通过比较中间元素与目标值的大小关系，决定向左还是向右继续搜索。

---

一、在有序数组上查找

二分搜索的两种形式

函数	功能	返回值
lower_bound(x)	第一个 >= x 的位置	第一个 >= x 的元素下标
upper_bound(x)	第一个 > x 的位置	第一个 > x 的元素下标

代码实现（C++）

// lower_bound: 第一个 >= x 的位置
int lower_bound(vector<int>& arr, int x) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

// upper_bound: 第一个 > x 的位置
int upper_bound(vector<int>& arr, int x) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] <= x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

Python 实现

import bisect

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

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

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

# 手动实现
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

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

经典例题：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)

代码实现（Python）：

import sys
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())))

def at_most(x):
    """返回 <= 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

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

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

---

二、在单调函数上查找

当我们需要在单调函数上进行二分搜索时，搜索的对象是一个布尔函数 f(x)。

基本概念

函数 f(x) 满足单调性： - 如果 f(x) = true，则 f(y) = true 对所有 y ≤ x（或 y ≥ x）

两种搜索模式

模式	函数	功能	无解时返回
找最大 true	last_true(lo, hi, f)	找最大的 x 使得 f(x)=true	lo - 1
找最小 true	first_true(lo, hi, f)	找最小的 x 使得 f(x)=true	hi + 1

函数 f(x) 的前置条件

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

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

例如，对于以下函数：

f(1) = true, f(2) = true, f(3) = true, f(4) = true, f(5) = true
f(6) = false, f(7) = false, f(8) = false

则 last_true(1, 8, f) = 5，first_true(1, 8, f) = 1。

代码实现

from typing import Callable

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

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

三、例题：最大中位数

题目来源: 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. 二分搜索：使用 last_true 找到最大的 x 使得所需操作数 ≤ k

代码实现

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

def last_true(lo, hi, f):
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if f(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 = last_true(1, int(2e9), med_reachable)
print(ans)

---

进阶例题：Cow Dance Show

题目来源: 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. 二分搜索：使用 first_true 找到最小的可行 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 first_true(lo, hi, f):
    """查找最小的 x 使得 f(x) = true"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

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

关键点分析

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

---

进阶例题：Convention（机场接机）

题目来源: 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. 二分搜索：使用 first_true 找到最小的可行 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 first_true(lo, hi, f):
    """查找最小的 x 使得 f(x) = true"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if f(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 = first_true(0, time[-1] - time[0], can_arrange)
print(ans)

原理解释

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

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

验证函数的三种情况（处理每头牛）： 1. 添加这头牛会导致第一头牛超过最大等待时间 → 开新大巴 2. 添加这头牛会导致大巴超载 → 开新大巴 3. 可以加入当前大巴

关键点分析

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

---

四、常见错误

错误 1：mid 取整方向错误

当 lo = 0, hi = 1 时，如果使用向下取整：

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

修复：根据搜索方向选择正确的取整方式 - 向右找 true → 向上取整 (hi - lo + 1) // 2 - 向左找 true → 向下取整 (hi - lo) // 2

错误 2：负数边界

mid = (lo + hi) // 2  # 对负数会向上取整！

修复：

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

错误 3：整数溢出

在 C++/Java 中，注意使用 long long 类型，避免 lo + hi 溢出。

---

五、总结

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

1. 在有序数组上：利用数组的有序性
2. 在单调函数上：利用函数的单调性

关键要点： - 确保函数是单调的 - 选择正确的 mid 取整方向 - 使用哨兵简化边界处理