WARNING

🧪 Beta公测版本提示：教程主体已完成，正在优化细节，欢迎大家提Issue反馈问题或建议。

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 上取整可避免死循环。

源码位置

clone 后打开（相对仓库根目录）：

docs/algorithms/strategy/divide-conquer/code/exercise.py