03_Binary Search 二分搜索

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

注意：确保不会对区间 [lo, hi] 外的值调用函数 f。

三、例题：最大中位数

题目来源: 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) 时间模拟演出过程

---

四、常见错误

错误 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 取整方向
• 使用哨兵简化边界处理