分治
简介
分治（divide and conquer），全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。
- 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
- 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。
二分查找和快速排序就用到了分治策略
如何判断分治问题
一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。
- 问题可以分解：原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
- 子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
- 子问题的解可以合并：原问题的解通过合并子问题的解得来。
常见应用
经典算法问题
- 寻找最近点对
- 大整数乘法
- 矩阵乘法
- 汉诺塔问题
- 求解逆序对
示例
二分查找
Python版本
def dfs(nums: list[int], target: int, i: int, j: int) -> int:
"""二分查找：问题 f(i, j)"""
# 若区间为空，代表无目标元素，则返回 -1
if i > j:
return -1
# 计算中点索引 m
m = (i + j) // 2
if nums[m] < target:
# 递归子问题 f(m+1, j)
return dfs(nums, target, m + 1, j)
elif nums[m] > target:
# 递归子问题 f(i, m-1)
return dfs(nums, target, i, m - 1)
else:
# 找到目标元素，返回其索引
return m
def binary_search(nums: list[int], target: int) -> int:
"""二分查找"""
n = len(nums)
# 求解问题 f(0, n-1)
return dfs(nums, target, 0, n - 1)
"""Driver Code"""
if __name__ == "__main__":
target = 6
nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]
# 二分查找（双闭区间）
index = binary_search(nums, target)
print("目标元素 6 的索引 = ", index)
Go版本
package main
import (
"fmt"
)
// dfs 递归实现 二分查找
func dfs(nums []int, target, i, j int) int {
if i > j {
return -1 // 若区间为空，返回 -1
}
m := (i + j) / 2 // 计算中点索引
if nums[m] < target {
return dfs(nums, target, m+1, j) // 递归搜索右半部分
} else if nums[m] > target {
return dfs(nums, target, i, m-1) // 递归搜索左半部分
} else {
return m // 找到目标元素，返回索引
}
}
// BinarySearch 二分查找的入口函数
func BinarySearch(nums []int, target int) int {
return dfs(nums, target, 0, len(nums)-1)
}
func main() {
target := 6
nums := []int{1, 3, 6, 8, 12, 15, 23, 26, 31, 35}
// 进行二分查找
index := BinarySearch(nums, target)
fmt.Printf("目标元素 %d 的索引 = %d\n", target, index)
}
寻找假币
一个袋子里有n个金币，其中存在一枚假币，假币和真币只有重量的区别。找出假币的位置，如果没找到，则返回 -1
def fakecoin(low: int, high: int, coins: list[int]):
sum1 = sum2 = 0
if low == high:
return high
if (high - low) == 1: # 说明数组只有两枚金币，返回重量较小的即可
if coins[high] < coins[low]:
return high
else:
return low
if (high - low + 1) % 2 == 0: #
mid = int((high - low + 1) / 2)
sum1 = sum(coins[low : low + mid])
sum2 = sum(coins[low + mid : high + 1])
if sum1 > sum2:
return fakecoin(low + mid, high, coins)
elif sum1 < sum2:
return fakecoin(low, low + mid - 1, coins)
elif (high - low + 1) % 2 != 0:
mid = int((high - low) / 2)
sum1 = sum(coins[low : low + mid])
sum2 = sum(coins[low + mid + 1 : high + 1])
if sum1 > sum2:
return fakecoin(low + mid + 1, high, coins)
elif sum1 < sum2:
return fakecoin(low, low + mid - 1, coins)
elif coins[low + mid] != coins[low]:
return low + mid
return -1
if __name__ == "__main__":
coins = [1, 1, 1, 1, 0, 1]
print(fakecoin(0, len(coins) - 1, coins))
汉诺塔
给定三根柱子，记为 A、B 和 C 。起始状态下，柱子 A 上套着 n 个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这 n 个圆盘移到柱子 C 上，并保持它们的原有顺序不变。在移动圆盘的过程中，需要遵守以下规则。
- 圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入。
- 每次只能移动一个圆盘。
- 小圆盘必须时刻位于大圆盘之上。
def move(src: list[int], tar: list[int]):
"""移动一个圆盘"""
# 从 src 顶部拿出一个圆盘
pan = src.pop()
# 将圆盘放入 tar 顶部
tar.append(pan)
def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
"""求解汉诺塔问题 f(i)"""
# 若 src 只剩下一个圆盘，则直接将其移到 tar
if i == 1:
move(src, tar)
return
# 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
dfs(i - 1, src, tar, buf)
# 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
move(src, tar)
# 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
dfs(i - 1, buf, src, tar)
def solve_hanota(A: list[int], B: list[int], C: list[int]):
"""求解汉诺塔问题"""
n = len(A)
# 将 A 顶部 n 个圆盘借助 B 移到 C
dfs(n, A, B, C)
"""Driver Code"""
if __name__ == "__main__":
# 列表尾部是柱子顶部
A = [5, 4, 3, 2, 1]
B = []
C = []
print("初始状态下：")
print(f"A = {A}")
print(f"B = {B}")
print(f"C = {C}")
solve_hanota(A, B, C)
print("圆盘移动完成后：")
print(f"A = {A}")
print(f"B = {B}")
print(f"C = {C}")