algo10 递归、分治与二分 — exercise.py 练习指南

Download exercise.py

练习目标

通过四个练习题，深入掌握分治法的递归结构、二分搜索的各种变体、以及将二分思想应用到不同场景的能力。

预备知识

在开始练习前，确保你已经理解了以下概念：

分治三步骤：分解(Divide) → 解决(Conquer) → 合并(Combine)
递归的基线条件和递归条件
二分搜索的标准实现和 lower_bound/upper_bound 变体
归并排序的 merge 操作和逆序对统计原理

任务清单

任务1：快速幂 `fast_pow(x, n)`

核心思想：利用分治将 $x^{n}$ 的 $O (n)$ 逐次乘法降到 $O (\log n)$ 。
递归关系：
- $x^{0} = 1$ （基线条件）
- $x^{n} = (x^{n / 2})^{2}$ （n 为偶数）
- $x^{n} = x \times (x^{n / 2})^{2}$ （n 为奇数）
示例： $2^{13}$ 的递归树深度仅 4 层（ $13 \to 6 \to 3 \to 1 \to 0$ ），而非 13 次乘法。
实现提示：先递归计算 half = fast_pow(x, n // 2)，再根据奇偶性决定返回值。

任务2：旋转排序数组搜索 `search_rotated_array(nums, target)`

问题描述：在 $[4, 5, 6, 7, 0, 1, 2]$ 这样的数组中找到 target 的位置。
关键洞察：虽然整体无序，但每次二分后，至少有一半是有序的。
- 如 mid=3(arr[3]=7)：左半 [4,5,6,7] 有序，右半 [0,1,2] 也有序但旋转了。
算法步骤：
1. 计算 mid，如果 nums[mid] == target 直接返回
2. 判断左半边是否有序：nums[lo] <= nums[mid]
3. 如果是：检查 target 是否在 [nums[lo], nums[mid]) 范围内
4. 如果不是：右半边有序，检查 target 是否在 (nums[mid], nums[hi]] 范围内
5. 缩小区间继续搜索

任务3：分治法求最大子数组和 `max_subarray_divide_conquer(nums)`

三种情况：最大子数组要么在左半边，要么在右半边，要么横跨中点。
横跨计算：
- 从中点向左扫描，计算以 mid 结尾的最大后缀和
- 从中点向右扫描，计算以 mid+1 开头的最大前缀和
- 横跨和 = 最大后缀和 + 最大前缀和
对比：Kadane 算法的 DP 解法 $O (n)$ 更简洁，但分治解法对理解"横跨"模式很有价值（这也是线段树的核心思想）。

任务4：二分答案——最大化最小段长度

问题模型："最大的最小值"或"最小的最大值"这类优化问题，若答案单调，可用二分答案。
单调性：如果最小段长 x 可行，那么所有 < x 的值也都可行。
check 函数：贪心扫描，如果两位置间距 ≥ x 就切一刀，统计能否切出 k 段。

提示

快速幂也可以用迭代实现（二进制展开），但递归版本更直观地展示了分治思想。
旋转数组搜索：注意处理重复元素的情况——当 nums[lo] == nums[mid] == nums[hi] 时，无法判断哪半有序，只能 lo += 1 或 hi -= 1。
最大子数组：注意所有元素为负数时，应返回最大的那个负数（单个元素），而非 0。
二分答案：注意二分循环中的取整方向——mid = (lo + hi + 1) // 2 上取整可避免死循环。

# -*- coding: utf-8 -*-
"""
algo10 递归、分治与二分 — 练习代码
==================================
请完成以下 TODO 任务，巩固对分治法和二分搜索的理解。
"""


# ============================================================================
# TODO 1: 实现快速幂（Binary Exponentiation / Fast Pow）
# ============================================================================
def fast_pow(x, n):
    """
    使用分治思想计算 x^n。
    核心思路：x^n = (x^(n/2))^2（当 n 为偶数），x^n = x * (x^(n/2))^2（当 n 为奇数）

    例如计算 x^13:
    x^13 = x * (x^6)^2
    x^6 = (x^3)^2
    x^3 = x * (x^1)^2
    x^1 = x * (x^0)^2 = x

    参数:
        x: 底数（float 或 int）
        n: 指数（非负整数）
    返回:
        x^n 的值
    """
    # TODO: 补全以下代码
    # 基线条件
    if n == 0:
        return 1.0  # 任何数的 0 次方 = 1

    # 递归条件：分治思想
    # half = fast_pow(x, n // 2)  ← 计算 x^(n/2)
    # if n % 2 == 0:
    #     return half * half      ← 偶数：x^n = (x^(n/2))^2
    # else:
    #     return _______________  ← 奇数：x^n = x * (x^(n/2))^2

    # TODO: 补全上面的递归实现
    return x ** n  # 临时占位


# ============================================================================
# TODO 2: 实现"在旋转排序数组中搜索"的二分搜索变体
# ============================================================================
def search_rotated_array(nums, target):
    """
    在旋转排序数组中搜索 target 的索引。
    旋转排序数组：一个有序数组在某点被旋转，如 [4,5,6,7,0,1,2]。

    思路：虽然整体不是有序的，但每次二分后，至少有一半是有序的。
    利用有序那一半判断 target 是否在其中。

    参数:
        nums: list，旋转排序数组
        target: 目标值
    返回:
        索引，-1 表示未找到
    """
    # TODO: 补全以下代码
    if not nums:
        return -1

    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = (lo + hi) // 2

        if nums[mid] == target:
            return mid

        # 判断哪半边是有序的
        # TODO: 如果左半边有序 (nums[lo] <= nums[mid])
        #   TODO: 如果 target 在左半边范围内，hi = mid - 1
        #   TODO: 否则 lo = mid + 1
        # TODO: 否则右半边有序
        #   TODO: 如果 target 在右半边范围内，lo = mid + 1
        #   TODO: 否则 hi = mid - 1
        pass  # ← TODO: 替换为完整实现

    return -1


# ============================================================================
# TODO 3: 实现分治法求最大子数组和（Maximum Subarray）
# ============================================================================
def max_subarray_divide_conquer(nums):
    """
    用分治法求解最大子数组和问题（Kadane DP O(n) 的替代方案）。
    分治思路：
    1. 数组从中点分成两半
    2. 最大子数组要么在左半边，要么在右半边，要么横跨中点
    3. 横跨中点的：从中点向左找最大后缀和 + 从中点向右找最大前缀和

    参数:
        nums: list，整数数组（可含负数）
    返回:
        最大子数组的和
    """
    def helper(lo, hi):
        # 基线条件：单个元素
        if lo == hi:
            return nums[lo]

        mid = (lo + hi) // 2

        # 递归求左右两边的最优解
        left_max = helper(lo, mid)
        right_max = helper(mid + 1, hi)

        # TODO: 计算横跨中点的最大子数组和
        # 从中点向左扫描，累加求和，记录最大后缀和
        # left_sum = float('-inf')
        # curr = 0
        # for i in range(mid, lo - 1, -1):
        #     curr += nums[i]
        #     left_sum = max(left_sum, curr)

        # 从中点向右扫描，累加求和，记录最大前缀和
        # right_sum = float('-inf')
        # curr = 0
        # for i in range(mid + 1, hi + 1):
        #     curr += nums[i]
        #     right_sum = max(right_sum, curr)

        # 横跨和 = left_sum + right_sum
        cross_max = float('-inf')  # TODO: 替换为正确值

        # 返回三者中的最大值
        return max(left_max, right_max, cross_max)

    if not nums:
        return 0
    return helper(0, len(nums) - 1)


# ============================================================================
# TODO 4: 实现二分答案：在 n 个木板间选 k 段，使最小段长度最大化
# ============================================================================
def maximize_min_segment_length(positions, k):
    """
    给定 n 个木板的坐标（已排序），需要放置 k-1 个切割点将木板分成 k 段。
    求使最小段长度最大化的切割方案，返回该最大化的最小段长度。

    思路（二分答案）：
    设答案为 x，检查能否将木板分成 k 段，每段长度 ≥ x。
    贪心扫描：从第一个位置开始，每次尽可能延申直到段长 ≥ x，计数段数。
    如果段数 ≥ k，则 x 可行。

    参数:
        positions: list of int，已排序的位置坐标
        k: 需要分成的段数
    返回:
        最大化的最小段长度（int）
    """
    def can_divide(min_len):
        """检查能否将 positions 分成 k 段，每段长度 >= min_len"""
        # TODO: 实现检查逻辑
        # segments = 0
        # last_pos = positions[0]
        # for pos in positions[1:]:
        #     if pos - last_pos >= min_len:
        #         segments += 1
        #         last_pos = pos
        # return segments + 1 >= k  (包括最后一段)
        return False  # TODO

    if not positions or k <= 1:
        return 0
    if k > len(positions):
        return 0

    # TODO: 二分搜索最大可行的最小段长度
    # lo = 0
    # hi = positions[-1] - positions[0]
    # while lo < hi:
    #     mid = (lo + hi + 1) // 2  # 上取整，避免死循环
    #     if can_divide(mid):
    #         lo = mid
    #     else:
    #         hi = mid - 1
    # return lo
    return 0  # TODO


# ============================================================================
# 测试代码
# ============================================================================
if __name__ == '__main__':
    print('=' * 50)
    print('algo10 递归、分治与二分 — 练习')
    print('=' * 50)

    # 测试 TODO 1: 快速幂
    print('\n--- TODO 1: 快速幂 ---')
    print(f'  2^10 = {fast_pow(2, 10)}  (期望: 1024)')
    print(f'  3^5  = {fast_pow(3, 5)}   (期望: 243)')
    print(f'  2^0  = {fast_pow(2, 0)}   (期望: 1)')

    # 测试 TODO 2: 旋转数组搜索
    print('\n--- TODO 2: 旋转排序数组搜索 ---')
    arr2 = [4, 5, 6, 7, 0, 1, 2]
    for t in [0, 3, 6]:
        print(f'  search_rotated_array({arr2}, {t}) = {search_rotated_array(arr2, t)}')

    # 测试 TODO 3: 分治法最大子数组和
    print('\n--- TODO 3: 分治法最大子数组和 ---')
    test_cases = [
        ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),        # 标准测试
        ([1, 2, 3, 4], 10),                            # 全正
        ([-1, -2, -3, -4], -1),                        # 全负
    ]
    for nums, expected in test_cases:
        result = max_subarray_divide_conquer(nums)
        status = '✓' if result == expected else f'✗ (got {result})'
        print(f'  {nums} → {result} {status}')

    # 测试 TODO 4: 二分答案
    print('\n--- TODO 4: 二分答案（最大化最小段长）---')
    positions = [0, 3, 4, 8, 9, 10]
    k = 3
    result = maximize_min_segment_length(positions, k)
    print(f'  位置: {positions}, k={k} → 最大最小段长 = {result}')

    print('\n提示: 请补全上方所有 TODO 函数后再运行测试。')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

algo10 递归、分治与二分 — exercise.py 练习指南 ​

练习目标 ​

预备知识 ​

任务清单 ​

任务1：快速幂 fast_pow(x, n) ​

任务2：旋转排序数组搜索 search_rotated_array(nums, target) ​

任务3：分治法求最大子数组和 max_subarray_divide_conquer(nums) ​

任务4：二分答案——最大化最小段长度 ​

提示 ​