DSA Interview Prep · 课时

答案空间上的二分查找

Q: 「答案空间上的二分查找」课时是免费的吗？

是的 — 「答案空间上的二分查找」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 「答案空间上的二分查找」这节课中我会学到什么？

将连续的答案范围视为搜索空间，解决完成任务的最短时间和运输包裹所需容量等问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

Q: 「答案空间上的二分查找」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

将连续的答案范围视为搜索空间，解决完成任务的最短时间和运输包裹所需容量等问题。

答案空间上的二分查找 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

在答案空间上进行二分查找

大多数人都知道如何在有序数组中使用二分查找来查找某个值。但将二分查找应用于可能答案的空间时，它的能力会更强。您不是在数组中查找，而是在数值范围内查找——例如“将所有包裹运送完所需的最少天数是多少？”——并使用检查函数来判断候选答案是否可行。

这种技术可以将许多优化问题的复杂度从 O(n²) 或更高降至 O(n log(max_answer))。

答案空间模板

该模板包含三个组成部分。首先，定义能够包围所有有效答案的搜索范围 [lo, hi]。其次，编写一个可行性检查 can_achieve(mid)，如果 mid 值可以实现，则返回 True。第三，在 [lo, hi] 上进行二分查找：如果 can_achieve(mid) 为真，就向更小（或更大）的答案移动；否则向另一个方向移动。

关键性质是：可行性函数必须具有单调性——一旦某个答案可行，其后的所有值也都可行（或者其前的所有值都不可行）。

# Generic template
def answer_space_search(lo, hi, is_feasible):
    result = hi  # or lo, depending on direction
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            result = mid
            hi = mid - 1   # try to minimise further
        else:
            lo = mid + 1
    return result

示例：包裹运输容量

LeetCode 1011“在 D 天内运输包裹的容量”：给定一个重量列表和 D 天，求在 D 天内按顺序运输所有包裹所需的最小运输容量。答案位于 [max(weights), sum(weights)] 之间。如果贪心模拟能够在 D 天内装运所有包裹，则该容量是可行的。对容量范围进行二分查找，时间复杂度为 O(n log(sum))。

def shipWithinDays(weights, days):
    def can_ship(capacity):
        needed_days, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                needed_days += 1
                current_load = 0
            current_load += w
        return needed_days <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid        # feasible, try smaller
        else:
            lo = mid + 1    # not feasible, need more capacity
    return lo

print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5))  # 15
print(shipWithinDays([3,2,2,4,1,4], 3))            # 6

示例：Koko 吃香蕉

LeetCode 875“Koko 吃香蕉”：Koko 每小时可以吃 K 根香蕉；她希望恰好在 H 小时内吃完 H 堆香蕉，并使 K 最小。搜索范围是 [1, max(piles)]。检查方式是：速率为 K 时，总耗时为每堆香蕉所需小时数 ceil(pile/K) 的总和，且必须 <= H。我们对满足条件的最小 K 进行二分查找。

import math

def minEatingSpeed(piles, h):
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid      # feasible, try lower speed
        else:
            lo = mid + 1  # too slow
    return lo

print(minEatingSpeed([3,6,7,11], 8))    # 4
print(minEatingSpeed([30,11,23,4,20], 5))  # 30

示例：制作花束所需的最少天数

LeetCode 1482“制作 m 束花所需的最少天数”：您需要制作 m 束花，每束由 k 朵连续开放的花组成。第 i 朵花在 bloomDay[i] 这一天开放。对天数进行二分查找，范围是 [1, max(bloomDay)]。可行性检查会统计连续开放的花朵数量，并判断能否组成 m 束花。单调性表明：如果第 d 天可行，那么第 d+1 天也可行。

def minDays(bloomDay, m, k):
    if m * k > len(bloomDay):
        return -1  # impossible

    def can_make(day):
        bouquets = consecutive = 0
        for bd in bloomDay:
            if bd <= day:
                consecutive += 1
                if consecutive == k:
                    bouquets += 1
                    consecutive = 0
            else:
                consecutive = 0
        return bouquets >= m

    lo, hi = 1, max(bloomDay)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_make(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(minDays([1,10,3,10,2], 3, 1))  # 3
print(minDays([1,10,3,10,2], 3, 2))  # -1

确定搜索范围

选择正确的 [lo, hi] 范围至关重要。lo 应该是可能的最小答案（例如最小元素、1 或 0），hi 应该是可能的最大答案（例如所有元素之和、最大元素或 n）。将 hi 设置得过小会漏掉有效答案；设置得过大则没有问题，因为二分查找仍会在 O(log(hi - lo)) 步内收敛。

# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating:      lo=1,            hi=max(piles)
# Square root:      lo=1,            hi=x
# Allocate books:   lo=max(pages),   hi=sum(pages)

def isqrt_bs(x):
    if x < 2:
        return x
    lo, hi = 1, x
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid * mid <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo - 1

for n in [0, 1, 4, 8, 9, 15, 16]:
    print(f'isqrt({n}) = {isqrt_bs(n)}')

最大化与最小化：方向很重要

答案空间二分查找有两种形式。最小化答案：检查通过时尝试更小的值（hi = mid）；检查失败时尝试更大的值（lo = mid + 1）。最大化答案：检查通过时尝试更大的值（lo = mid + 1，并将 mid 保存为候选值）；检查失败时尝试更小的值（hi = mid - 1）。编写代码前，请始终明确要搜索的方向。

# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
    result = lo - 1   # sentinel: no feasible answer found
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            result = mid
            lo = mid + 1  # try larger
        else:
            hi = mid - 1
    return result

# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50))  # 7

最小页数分配（经典问题）

给定 n 本书（页数数组）和 k 名学生，请连续分配这些书，使阅读页数最多的学生所读页数尽可能少。对答案进行二分查找（可能的最小最大值）。可行性检查会使用贪心策略为学生分配书籍：当再添加一本书会超过当前最大页数时，就将这本书分配给一名新学生。如果所需学生数 <= k，则该最大页数可行。

def allocate_min_pages(pages, k):
    if k > len(pages):
        return -1

    def is_feasible(max_pages):
        students, current = 1, 0
        for p in pages:
            if p > max_pages:
                return False  # single book exceeds limit
            if current + p > max_pages:
                students += 1
                current = 0
            current += p
        return students <= k

    lo, hi = max(pages), sum(pages)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(allocate_min_pages([12, 34, 67, 90], 2))  # 113
print(allocate_min_pages([10, 20, 30, 40], 2))  # 60

答案空间搜索的复杂度分析

时间复杂度为O(n × log(range))，其中 n 是可行性检查的成本（通常是线性扫描），range = hi - lo 是范围大小，也就是答案空间的大小。例如，如果所有页数之和为 10⁹，且可行性检查为 O(n)，那么总时间复杂度为 O(n log 10⁹) ≈ O(30n)，远优于 O(n²) 的暴力枚举。

二分查找本身的空间复杂度为O(1)，此外还要加上可行性检查所使用的空间。

import math

# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9         # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9)  # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')

有序矩阵中的第 k 小元素

LeetCode 378“有序矩阵中的第 k 小元素”：一个 n×n 矩阵的每一行和每一列都已排序。对答案值进行二分查找，范围是 [matrix[0][0], matrix[n-1][n-1]]。可行性检查从左下角开始使用指针，统计小于等于 mid 的元素数量，时间复杂度为 O(n)。找到至少有 k 个元素小于等于 mid 时的最小值。

def kthSmallest(matrix, k):
    n = len(matrix)

    def count_le(mid):
        count, row, col = 0, n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    lo, hi = matrix[0][0], matrix[n-1][n-1]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8))  # 13

识别答案空间问题

适合使用答案空间二分查找的问题通常具有以下信号：问题要求一个最小值或最大值，答案位于有界的数值范围内，并且增大（或减小）候选答案会使可行性单调变好或变坏。典型关键词包括“可能的最小最大值”、“最多 k 次操作”以及“在 d 天内”。

发现这些信号后，请立即定义 lo 和 hi，编写可行性函数，并应用模板。这种结构化方法在面试中很少出错。

快速检查

请测试您对本课数据结构与算法——编码面试准备相关概念的理解。

课程回顾

在本课中，您学到了：当可行性函数在数值范围内具有单调性时，可以使用答案空间二分查找；该模板搜索 [lo, hi]，并使用可达性检查将搜索空间不断缩小一半；以及总复杂度为 O(n log(range))，其中 n 是一次可行性检查的成本。接下来我们将学习链表和节点类。

常见问题解答