03_Binary Search 二分搜索

Binary Search 二分搜索

什么是二分搜索？

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

基本思想

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

二分搜索的两种形式

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

代码实现

// 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;
}

---

经典例题：Counting Haybales

题目来源: USACO - Haybales

题目描述

给定 N 个不同位置的干草捆（有 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)

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("haybales.in", "r", stdin);
    freopen("haybales.out", "w", stdout);

    int N, Q;
    cin >> N >> Q;

    vector<int> pos(N);
    for (int i = 0; i < N; i++) {
        cin >> pos[i];
    }
    sort(pos.begin(), pos.end());

    // 自定义 upper_bound：返回第一个 > x 的位置
    auto count_leq = [&](int x) -> int {
        // 使用 STL 的 upper_bound
        return upper_bound(pos.begin(), pos.end(), x) - pos.begin();
    };

    for (int i = 0; i < Q; i++) {
        int A, B;
        cin >> A >> B;
        int ans = count_leq(B) - count_leq(A - 1);
        cout << ans << "\n";
    }

    return 0;
}

代码实现（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: int) -> int:
    """返回 <= x 的元素个数"""
    lo = 0
    hi = 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())
    ans = at_most(b) - at_most(a - 1)
    print(ans)

时间复杂度

• 排序：O(N log N)
• 单次查询：O(log N)
• 总时间：O(N log N + Q log N)

---

二分搜索在单调函数上的应用

当我们需要在单调函数上进行二分搜索时，其核心思想与在有序数组上进行二分搜索类似，但搜索的对象是一个布尔函数 f(x)。

基本概念

假设我们有一个布尔函数 f(x)，通常我们需要找到满足 f(x) = true 的最大或最小的 x 值。与在有序数组上进行二分搜索类似，二分搜索只在函数是单调的时候才有效，即函数值是总是非递减或总是非递增的。

查找最大的满足条件的 x

我们希望构造一个函数 lastTrue(lo, hi, f)，返回在范围 [lo, hi] 中满足 f(x) = true 的最大 x 值。如果没有这样的 x 存在，则返回 lo - 1。

这可以通过二分搜索实现，前提是 f(x) 满足以下两个条件： 1. 如果 f(x) = true，那么对于所有 y ≤ x，都有 f(y) = true 2. 如果 f(x) = false，那么对于所有 y ≥ x，都有 f(y) = false

实现方式 1

from typing import Callable

def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """
    二分搜索：查找最大的 x 使得 f(x) = true
    :param lo: 下界
    :param hi: 上界
    :param f: 返回数字是否有效的函数
    :return: 满足 f(x) = true 的最大 x，如果不存在则返回 lo - 1
    """
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整，避免死循环
        if f(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

实现方式 2（基于区间跳跃）

from typing import Callable

def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """
    二分搜索：查找最大的 x 使得 f(x) = true
    :param lo: 下界
    :param hi: 上界
    :param f: 返回数字是否有效的函数
    :return: 满足 f(x) = true 的最大 x，如果不存在则返回 lo - 1
    """
    for i in range(60, -1, -1):
        mid = lo + (1 << i)
        if mid <= hi and f(mid):
            lo = mid
    return lo

查找最小的满足条件的 x

我们希望构造一个函数 firstTrue(lo, hi, f)，返回在范围 [lo, hi] 中满足 f(x) = true 的最小 x 值。如果没有这样的 x 存在，则返回 hi + 1。

类似地，如果 f(x) 满足以下条件，可以使用二分搜索： 1. 如果 f(x) = true，那么对于所有 y ≥ x，都有 f(y) = true 2. 如果 f(x) = false，那么对于所有 y ≤ x，都有 f(y) = false

from typing import Callable

def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """
    二分搜索：查找最小的 x 使得 f(x) = true
    :param lo: 下界
    :param hi: 上界
    :param f: 返回数字是否有效的函数
    :return: 满足 f(x) = true 的最小 x，如果不存在则返回 hi + 1
    """
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2  # 向下取整
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

---

示例：最大中位数

题目描述

给定一个包含 n 个整数的数组 arr（n 为奇数），我们可以对数组进行 k 次操作：每次选择数组中的任意一个元素并将其加 1。我们希望使数组的中位数尽可能大。

约束条件：1 ≤ n ≤ 2 × 10^5，1 ≤ k ≤ 10^9，n 为奇数。

解题思路

1. 首先将数组排序

2. 为了将中位数增加到 x，需要将数组后半部分的所有元素都增加到至少 x

3. 将中位数提高到 x 所需的操作次数为： $$\sum_{i=(n+1)/2}^{n} \max(0, x - arr[i])$$

4. 如果所需操作次数 ≤ k，则 x 可以作为中位数

5. 使用上界二分搜索找到满足条件的最大 x 值

代码实现

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)

输入输出格式

• 输入：第一行 n k，第二行 n 个整数
• 输出：最大可达中位数

---

常见错误

错误 1：边界处理错误（Off By One）

考虑以下代码：

def f(x: int) -> int:
    return x * x

def sqrt(x: int) -> int:
    lo = 0
    hi = 0
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid) <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo

当 lo = 0 且 hi = 1 时，这会导致无限循环！修复方法是将中值计算改为向上取整：

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

错误 2：未考虑负数边界

考虑 firstTrue 的以下版本：

def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    hi += 1
    while lo < hi:
        mid = (lo + hi) // 2  # 对负数会向上取整！
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

当 lo 为负数时，上述代码可能不工作。例如：

# 输出 -8 而不是 -9
print(first_true(-10, -10, lambda x: False))
# 导致无限循环
print(first_true(-10, -10, lambda x: True))

这是因为将奇数负整数除以 2 会向上取整而不是向下取整。

修复方法是使用：

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

错误 3：整数溢出

第一个版本的 firstTrue 在 hi - lo 初始值超过 INT_MAX 时无法工作，而第二个版本如果在执行过程中 lo + hi 超过 INT_MAX 也将无法工作。在 Python 中整数可以自动扩展，但在大整数类型受限的语言（如 C++/Java）中，需要注意使用 long long 类型。

---

总结

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

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

关键要点： - 确保函数是单调的（单调递增或单调递减） - 注意边界条件的处理（特别是负数情况） - 选择正确的取整方向以避免无限循环