分治算法的应用
归并排序
归并排序是成功应用分治策略的一个完美例子，对于给定一组序列含 n 个数组 A[0..n-1]，归并排序将其一分为二：A[0..⌊n/2⌋-1] 和 A[⌊n/2⌋..⌊n-1⌋]，并对每个子数组递归排序，然后将这两个排好序的子数组合并为一个有序数组。
Go 代码如下：
func mergeSort(items []int) []int { if len(items) < 2 { return items } first := mergeSort(items[:len(items)/2]) second := mergeSort(items[len(items)/2:]) return merge(first, second) }
让我们先编写 mergeSort() 函数。它是一个递归函数，这意味着它会调用自己，在这种情况下，它实际上会调用自己两次。 mergeSort 函数的要点是将数组分成大致相等的两个部分，在这些部分上调用自身，然后调用 merge() 将这些部分重新组合在一起。
merge() 函数用于将两个排序列表合并回一个排序列表，这是真正发生“魔术”的地方。在递归的最低级别，两个“排序”列表的长度均为 1。这些单元素列表将合并为长度为 2 的排序列表，我们可以从那里构建。然后写出归并的 merge() 函数：
func merge(a []int, b []int) []int { final := []int{} i := 0 j := 0 for i < len(a) && j < len(b) { if a[i] < b[j] { final = append(final, a[i]) i++ } else { final = append(final, b[j]) j++ } } for ; i < len(a); i++ { final = append(final, a[i]) } for ; j < len(b); j++ { final = append(final, b[j]) } return final }
然后在 main() 函数中验证：
func main() { unsorted := []int{8, 3, 2, 9, 7, 1, 5, 4} sorted := mergeSort(unsorted) fmt.Println(sorted) // sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9] }
二分查找
目的：在一个含有 N 个元素的有序数组中有效地的定位目标值。
思想：假设在有序数组 arr 中查找元素 k，返回 k 所在的下标（索引值）。设 arr[low,high] 是当前的查找区间，确定该区间的中间位置 mid=⌊(low+high)//2⌋ ，然后将待查的 k 值与 arr[mid] 比较:
- 若
k==arr[mid]，说明找到 k，则查找成功并且终止，则找到该元素； - 若
k<arr[mid]，根据数组有序的前提，目标值 k 在左边的区域中，索引的范围改为[low, mid-1] - 若
k>arr[mid]，目标值在右边的区域中，查找索引范围改为[mid+1, high]
示例：
输入 nums = [-1,0,3,5,9,12], target = 9 输出 4 解释 9 出现在 nums 中并且下标为 4
Python 代码如下：
class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # 在区间 [left, right] 内查找 target while left < right: # 取区间中间节点 mid = left + (right - left) // 2 # nums[mid] 小于目标值，排除掉不可能区间 [left, mid]，在 [mid + 1, right] 中继续搜索 if nums[mid] < target: left = mid + 1 # nums[mid] 大于等于目标值，目标元素可能在 [left, mid] 中，在 [left, mid] 中继续搜索 else: right = mid # 判断区间剩余元素是否为目标元素，不是则返回 -1 return left if nums[left] == target else -1
其他应用
快速排序也是另一种基于分治算法的重要排序算法，不像归并排序是按照元素数组中的位置对它们进行划分，快速排序是按照元素的值对它们进行划分。
二叉树遍历中前序、中序和后序遍历都可以用到分治，因为二叉树本身的定义就是将同样类型的树分为两个更小的组成部分——左子树和右子树。
其他如大整数乘法和 Strassen 矩阵乘法也可以巧妙的运用分治算法来获得更好的渐近效率，感兴趣的读者可以继续探索。
