分治算法详解

分治算法（Divide and Conquer）是一种重要的算法设计思想，它将一个复杂的问题分解成若干个相同或相似的子问题，递归地解决这些子问题，然后将子问题的解合并成原问题的解。本文将从概念到实践，全面讲解分治算法的思想、适用场景及常见题型。

---

一、什么是分治算法？

1.1 分治算法的定义

分治算法（Divide and Conquer）是一种将复杂问题分解为若干个相同或相似的子问题，递归地解决这些子问题，然后将子问题的解合并成原问题的解的算法设计思想。

核心思想：

• 分（Divide）：将原问题分解为若干个规模较小的子问题
• 治（Conquer）：递归地解决这些子问题
• 合（Combine）：将子问题的解合并成原问题的解

通俗理解：

想象你要统计全校学生的身高平均值。

• 直接方法：一个人统计全校，工作量巨大
• 分治方法：
  • 把全校分成各个班级（分）
  • 每个班级统计自己的平均值（治）
  • 把各班级的结果合并，得到全校平均值（合）

---

1.2 分治算法的三个步骤

┌─────────────────────────────────────────────────────────────────┐
│                   分治算法三步骤                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌─────────┐     ┌─────────┐     ┌─────────┐                   │
│  │   分    │ ──▶ │   治    │ ──▶ │   合    │                   │
│  │ Divide  │     │ Conquer │     │ Combine │                   │
│  └─────────┘     └─────────┘     └─────────┘                   │
│                                                                 │
│  1. 分解（Divide）                                               │
│     └── 将原问题分解为若干个规模较小的子问题                      │
│     └── 子问题与原问题类型相同，但规模更小                        │
│                                                                 │
│  2. 解决（Conquer）                                              │
│     └── 递归地解决各个子问题                                      │
│     └── 如果子问题足够小，直接求解（递归终止条件）                 │
│                                                                 │
│  3. 合并（Combine）                                              │
│     └── 将子问题的解合并成原问题的解                              │
│     └── 合并过程可能涉及额外的计算                                │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

---

1.3 分治算法的特点

特点	说明
问题分解	原问题可以分解为若干个相同类型的子问题
子问题独立	子问题之间相互独立，没有重叠
最优子结构	问题的最优解包含子问题的最优解
递归求解	通常使用递归实现
合并代价	子问题解的合并可能需要额外计算

---

1.4 分治 vs 其他算法

算法	策略	特点
分治算法	分解 → 解决 → 合并	子问题独立，可能重复计算
动态规划	分解 → 记忆化 → 合并	子问题重叠，避免重复计算
贪心算法	局部最优	不回溯，效率高
回溯算法	尝试所有可能	可回退，找到所有解

---

二、分治算法的核心思想

2.1 适用条件

一个问题能用分治算法解决，必须满足以下条件：

条件一：问题可分解

原问题可以分解为若干个规模较小的相同问题。

示例：

• 排序问题：大数组排序 → 两个小数组排序
• 查找问题：大范围查找 → 两个小范围查找

---

条件二：子问题独立

子问题之间相互独立，一个子问题的解不影响其他子问题。

对比：

• 分治：子问题独立（归并排序的两个子数组）
• 动态规划：子问题重叠（斐波那契数列）

---

条件三：子问题可合并

子问题的解可以合并成原问题的解。

示例：

• 归并排序：两个有序数组合并成一个有序数组
• 快速排序：确定枢轴位置后，左右子数组自然有序

---

条件四：有终止条件

子问题规模足够小时，可以直接求解。

示例：

• 数组长度为 1 时，已经是有序的
• 查找范围为 1 个元素时，直接比较即可

---

2.2 分治算法的解题步骤

┌─────────────────────────────────────────────────────────────────┐
│                   分治算法解题步骤                               │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. 分解（Divide）                                               │
│     └── 确定分解策略（二分、多分）                               │
│     └── 将问题分解为子问题                                       │
│                                                                 │
│  2. 递归求解（Conquer）                                          │
│     └── 递归调用解决子问题                                       │
│     └── 检查终止条件（子问题足够小）                              │
│                                                                 │
│  3. 合并（Combine）                                              │
│     └── 将子问题的解合并                                         │
│     └── 处理合并过程中的额外计算                                  │
│                                                                 │
│  4. 返回结果                                                     │
│     └── 返回合并后的结果                                         │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

---

2.3 分治算法的复杂度分析

时间复杂度

分治算法的时间复杂度通常可以用主定理（Master Theorem）计算：

T(n) = aT(n/b) + f(n)

其中：
- a：子问题的个数
- n/b：每个子问题的规模
- f(n)：分解和合并的代价

常见情况：

算法	递推式	时间复杂度
二分查找	T(n) = T(n/2) + O(1)	O(log n)
归并排序	T(n) = 2T(n/2) + O(n)	O(n log n)
快速排序（平均）	T(n) = 2T(n/2) + O(n)	O(n log n)
快速排序（最坏）	T(n) = T(n-1) + O(n)	O(n²)
矩阵乘法（Strassen）	T(n) = 7T(n/2) + O(n²)	O(n^2.807)

---

空间复杂度

算法	空间复杂度	说明
二分查找	O(log n)	递归栈深度
归并排序	O(n)	需要额外数组
快速排序	O(log n)	递归栈深度

---

三、经典分治算法

3.1 归并排序（Merge Sort）

思想：

• 将数组分成两半
• 分别对两半进行排序
• 将两个有序数组合并成一个有序数组

代码实现：

function mergeSort(arr) {
  // 终止条件：数组长度为 1 时，已经是有序的
  if (arr.length <= 1) {
    return arr;
  }
  
  // 1. 分解：将数组分成两半
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // 2. 递归排序左右两半
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  
  // 3. 合并两个有序数组
  return merge(sortedLeft, sortedRight);
}

// 合并两个有序数组
function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  
  // 比较两个数组的元素，按顺序放入结果
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  
  // 将剩余的元素放入结果
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }
  
  return result;
}

// 测试
console.log(mergeSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

时间复杂度： O(n log n)
空间复杂度： O(n)

---

3.2 快速排序（Quick Sort）

思想：

• 选择一个枢轴元素
• 将数组分成两部分：小于枢轴的和大于枢轴的
• 递归排序两部分

代码实现：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 获取枢轴位置
    const pivotIndex = partition(arr, left, right);
    
    // 递归排序左右两部分
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

// 分区函数
function partition(arr, left, right) {
  // 选择最右边的元素作为枢轴
  const pivot = arr[right];
  let i = left - 1;  // i 指向小于枢轴的最后一个元素
  
  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      // 交换 arr[i] 和 arr[j]
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  // 将枢轴放到正确位置
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  
  return i + 1;
}

// 测试
console.log(quickSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

时间复杂度：

• 平均：O(n log n)
• 最坏：O(n²) —— 数组已经有序时

空间复杂度： O(log n) —— 递归栈深度

---

3.3 二分查找（Binary Search）

思想：

• 在有序数组中查找目标值
• 每次将查找范围缩小一半

代码实现：

// 递归实现
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 终止条件：查找范围为空
  if (left > right) {
    return -1;
  }
  
  const mid = Math.floor((left + right) / 2);
  
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    // 在右半部分查找
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    // 在左半部分查找
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

// 迭代实现
function binarySearchIterative(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

// 测试
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearchRecursive(arr, 7));  // 3
console.log(binarySearchIterative(arr, 7));  // 3
console.log(binarySearchRecursive(arr, 4));  // -1

时间复杂度： O(log n)
空间复杂度：

• 递归：O(log n)
• 迭代：O(1)

---

四、经典例题详解

4.1 例题一： Pow(x, n)

题目：
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数。

示例：

输入: x = 2.00000, n = 10
输出: 1024.00000

输入: x = 2.10000, n = 3
输出: 9.26100

---

解法：快速幂（分治）

思想：

• x^n = x^(n/2) × x^(n/2) —— n 为偶数
• x^n = x^((n-1)/2) × x^((n-1)/2) × x —— n 为奇数

代码实现：

function myPow(x, n) {
  // 处理负数指数
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }
  
  return fastPow(x, n);
}

function fastPow(x, n) {
  // 终止条件
  if (n === 0) return 1;
  if (n === 1) return x;
  
  // 分治：计算 x^(n/2)
  const half = fastPow(x, Math.floor(n / 2));
  
  // 合并
  if (n % 2 === 0) {
    // n 为偶数
    return half * half;
  } else {
    // n 为奇数
    return half * half * x;
  }
}

// 测试
console.log(myPow(2.0, 10));  // 1024
console.log(myPow(2.1, 3));   // 9.261
console.log(myPow(2.0, -2));  // 0.25

时间复杂度： O(log n)
空间复杂度： O(log n)

---

4.2 例题二：多数元素

题目：
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入: nums = [3,2,3]
输出: 3

输入: nums = [2,2,1,1,1,2,2]
输出: 2

---

解法一：分治法

思想：

• 将数组分成两半
• 分别找出左半部分和右半部分的众数
• 合并：比较两个众数在整个数组中的出现次数

代码实现：

function majorityElement(nums) {
  return majorityElementRec(nums, 0, nums.length - 1);
}

function majorityElementRec(nums, left, right) {
  // 终止条件：只有一个元素
  if (left === right) {
    return nums[left];
  }
  
  // 分解：将数组分成两半
  const mid = Math.floor((left + right) / 2);
  
  // 递归求解左右两半的众数
  const leftMajority = majorityElementRec(nums, left, mid);
  const rightMajority = majorityElementRec(nums, mid + 1, right);
  
  // 合并：如果左右众数相同，直接返回
  if (leftMajority === rightMajority) {
    return leftMajority;
  }
  
  // 否则，比较两个众数在整个区间的出现次数
  const leftCount = countInRange(nums, leftMajority, left, right);
  const rightCount = countInRange(nums, rightMajority, left, right);
  
  return leftCount > rightCount ? leftMajority : rightMajority;
}

// 统计某个数在区间内的出现次数
function countInRange(nums, num, left, right) {
  let count = 0;
  for (let i = left; i <= right; i++) {
    if (nums[i] === num) count++;
  }
  return count;
}

// 测试
console.log(majorityElement([3, 2, 3]));           // 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2

时间复杂度： O(n log n)
空间复杂度： O(log n)

---

解法二：Boyer-Moore 投票算法（更优）

function majorityElement(nums) {
  let candidate = null;
  let count = 0;
  
  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }
    count += (num === candidate) ? 1 : -1;
  }
  
  return candidate;
}

时间复杂度： O(n)
空间复杂度： O(1)

---

4.3 例题三：计算右侧小于当前元素的个数

题目：
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入: nums = [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

---

解法：归并排序变形

思想：

• 在归并排序的过程中统计逆序对
• 当左半部分的元素大于右半部分的元素时，产生逆序对

代码实现：

function countSmaller(nums) {
  const n = nums.length;
  const result = new Array(n).fill(0);
  
  // 记录每个元素的原始索引
  const indexedNums = nums.map((num, index) => ({ num, index }));
  
  mergeSortAndCount(indexedNums, 0, n - 1, result);
  
  return result;
}

function mergeSortAndCount(arr, left, right, result) {
  if (left >= right) return;
  
  const mid = Math.floor((left + right) / 2);
  
  // 递归排序左右两半
  mergeSortAndCount(arr, left, mid, result);
  mergeSortAndCount(arr, mid + 1, right, result);
  
  // 合并并统计
  mergeAndCount(arr, left, mid, right, result);
}

function mergeAndCount(arr, left, mid, right, result) {
  const temp = [];
  let i = left;      // 左半部分指针
  let j = mid + 1;   // 右半部分指针
  
  // 统计逆序对
  while (i <= mid && j <= right) {
    if (arr[i].num <= arr[j].num) {
      // 没有逆序对
      temp.push(arr[i]);
      i++;
    } else {
      // 发现逆序对：arr[i] > arr[j]
      // 说明 arr[i...mid] 都大于 arr[j]
      // 对于 arr[i]，右侧有 (mid - i + 1) 个元素小于它
      result[arr[i].index] += (mid - i + 1);
      temp.push(arr[j]);
      j++;
    }
  }
  
  // 处理剩余元素
  while (i <= mid) {
    temp.push(arr[i]);
    i++;
  }
  while (j <= right) {
    temp.push(arr[j]);
    j++;
  }
  
  // 复制回原数组
  for (let k = 0; k < temp.length; k++) {
    arr[left + k] = temp[k];
  }
}

// 测试
console.log(countSmaller([5, 2, 6, 1]));  // [2, 1, 1, 0]
console.log(countSmaller([-1]));          // [0]
console.log(countSmaller([-1, -1]));      // [0, 0]

时间复杂度： O(n log n)
空间复杂度： O(n)

---

4.4 例题四：数组中的第 K 个最大元素

题目：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

---

解法：快速选择（Quick Select）

思想：

• 基于快速排序的分区思想
• 每次分区后，确定枢轴的位置
• 根据枢轴位置决定继续在左半部分还是右半部分查找

代码实现：

function findKthLargest(nums, k) {
  // 第 k 大 = 第 (n - k) 小（0-based）
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(nums, left, right, k) {
  if (left === right) {
    return nums[left];
  }
  
  // 分区
  const pivotIndex = partition(nums, left, right);
  
  if (pivotIndex === k) {
    return nums[k];
  } else if (pivotIndex < k) {
    // 在右半部分查找
    return quickSelect(nums, pivotIndex + 1, right, k);
  } else {
    // 在左半部分查找
    return quickSelect(nums, left, pivotIndex - 1, k);
  }
}

function partition(nums, left, right) {
  // 随机选择枢轴（避免最坏情况）
  const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  [nums[randomIndex], nums[right]] = [nums[right], nums[randomIndex]];
  
  const pivot = nums[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

// 测试
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));  // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4));  // 4

时间复杂度：

• 平均：O(n)
• 最坏：O(n²) —— 随机化后概率极低

空间复杂度： O(log n)

---

4.5 例题五：为运算表达式设计优先级

题目：
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算出并返回所有可能组合的结果。你可以按任意顺序返回答案。

示例：

输入: expression = "2-1-1"
输出: [0,2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2

输入: expression = "2*3-4*5"
输出: [-34,-14,-10,-10,10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

---

解法：分治

思想：

• 遍历每个运算符，将其作为最后计算的运算符
• 左边部分和右边部分分别递归计算所有可能结果
• 合并左右结果，根据运算符计算最终结果

代码实现：

function diffWaysToCompute(expression) {
  const result = [];
  
  // 遍历每个字符
  for (let i = 0; i < expression.length; i++) {
    const char = expression[i];
    
    // 如果是运算符，将其作为分割点
    if (char === '+' || char === '-' || char === '*') {
      // 递归计算左边部分的所有结果
      const leftResults = diffWaysToCompute(expression.substring(0, i));
      // 递归计算右边部分的所有结果
      const rightResults = diffWaysToCompute(expression.substring(i + 1));
      
      // 合并左右结果
      for (const left of leftResults) {
        for (const right of rightResults) {
          if (char === '+') {
            result.push(left + right);
          } else if (char === '-') {
            result.push(left - right);
          } else if (char === '*') {
            result.push(left * right);
          }
        }
      }
    }
  }
  
  // 如果没有运算符，说明是纯数字
  if (result.length === 0) {
    result.push(parseInt(expression));
  }
  
  return result;
}

// 测试
console.log(diffWaysToCompute("2-1-1"));     // [0, 2]
console.log(diffWaysToCompute("2*3-4*5"));   // [-34, -14, -10, -10, 10]

时间复杂度： 取决于表达式结构，最坏 O(2^n)
空间复杂度： O(n) —— 递归栈深度

---

4.6 例题六：合并 K 个升序链表

题目：
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：

输入: lists = [[1,4,5],[1,3,4],[2,6]]
输出: [1,1,2,3,4,4,5,6]

---

解法：分治合并

思想：

• 将 K 个链表分成两半
• 分别合并左半部分和右半部分
• 合并两个有序链表

代码实现：

function mergeKLists(lists) {
  if (lists.length === 0) return null;
  return mergeLists(lists, 0, lists.length - 1);
}

function mergeLists(lists, left, right) {
  // 终止条件
  if (left === right) {
    return lists[left];
  }
  
  // 分解
  const mid = Math.floor((left + right) / 2);
  
  // 递归合并左右两部分
  const leftList = mergeLists(lists, left, mid);
  const rightList = mergeLists(lists, mid + 1, right);
  
  // 合并两个有序链表
  return mergeTwoLists(leftList, rightList);
}

function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let current = dummy;
  
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
  
  current.next = l1 || l2;
  return dummy.next;
}

// 测试
function createList(arr) {
  const dummy = { val: 0, next: null };
  let current = dummy;
  for (const val of arr) {
    current.next = { val, next: null };
    current = current.next;
  }
  return dummy.next;
}

function printList(head) {
  const result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  return result;
}

const lists = [
  createList([1, 4, 5]),
  createList([1, 3, 4]),
  createList([2, 6])
];
console.log(printList(mergeKLists(lists)));  // [1, 1, 2, 3, 4, 4, 5, 6]

时间复杂度： O(N log k) —— N 是总节点数，k 是链表数
空间复杂度： O(log k) —— 递归栈深度

---

4.7 例题七：搜索二维矩阵 II

题目：
编写一个高效的算法来搜索 m × n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例：

输入: matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
], target = 5
输出: true

---

解法：分治（二分查找变形）

思想：

• 利用矩阵的有序性
• 从右上角或左下角开始，每次可以排除一行或一列

代码实现（分治版本）：

function searchMatrix(matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) return false;
  
  return searchRecursive(matrix, target, 0, 0, matrix.length - 1, matrix[0].length - 1);
}

function searchRecursive(matrix, target, top, left, bottom, right) {
  // 终止条件
  if (top > bottom || left > right) return false;
  
  // 取中间行
  const midRow = Math.floor((top + bottom) / 2);
  
  // 在该行进行二分查找
  const col = binarySearchRow(matrix[midRow], target, left, right);
  
  if (col >= 0 && matrix[midRow][col] === target) {
    return true;
  }
  
  // 在左下或右上区域继续搜索
  // 因为 matrix[midRow][col] > target，所以目标在上方或左方
  // 因为 matrix[midRow][col+1] < target（如果存在），所以目标在下方或右方
  
  // 搜索左下区域
  if (searchRecursive(matrix, target, midRow + 1, left, bottom, col)) {
    return true;
  }
  
  // 搜索右上区域
  if (searchRecursive(matrix, target, top, col + 1, midRow - 1, right)) {
    return true;
  }
  
  return false;
}

function binarySearchRow(row, target, left, right) {
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (row[mid] === target) {
      return mid;
    } else if (row[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return right;  // 返回小于 target 的最大索引
}

// 更简单的解法（非分治，但利用了有序性）
function searchMatrixSimple(matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) return false;
  
  let row = 0;
  let col = matrix[0].length - 1;
  
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      col--;  // 当前值太大，向左移动
    } else {
      row++;  // 当前值太小，向下移动
    }
  }
  
  return false;
}

// 测试
const matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
];
console.log(searchMatrixSimple(matrix, 5));   // true
console.log(searchMatrixSimple(matrix, 20));  // false

时间复杂度： O(m + n) —— 简单解法
空间复杂度： O(1)

---

五、分治算法 vs 其他算法

5.1 分治 vs 递归

特性	分治算法	递归
关系	分治使用递归实现	递归是一种编程技巧
结构	分 → 治 → 合	函数调用自身
适用	可分解的问题	任何可递归定义的问题
示例	归并排序、快速排序	斐波那契、阶乘

关系：

• 分治算法通常使用递归来实现
• 但递归不一定用于分治（如树的遍历）

---

5.2 分治 vs 动态规划

特性	分治算法	动态规划
子问题	相互独立	相互重叠
重复计算	可能重复计算	避免重复计算（记忆化）
典型问题	归并排序、快速排序	背包问题、最长子序列
时间复杂度	通常较低	通常较高

对比示例：

斐波那契数列：

// 分治（递归）—— 有大量重复计算
function fibDivideConquer(n) {
  if (n <= 1) return n;
  return fibDivideConquer(n - 1) + fibDivideConquer(n - 2);
}
// 时间复杂度：O(2^n)

// 动态规划 —— 避免重复计算
function fibDP(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
// 时间复杂度：O(n)

---

5.3 分治 vs 贪心

特性	分治算法	贪心算法
策略	分解解决所有子问题	每步选局部最优
正确性	一定能得到正确解	不一定得到最优解
回溯	不需要回溯	不回溯
典型问题	排序、查找	区间调度、哈夫曼编码

---

六、分治算法的题型分类

6.1 按问题类型分类

类型一：排序问题

算法	思想	时间复杂度
归并排序	分半排序，然后合并	O(n log n)
快速排序	分区排序	O(n log n)

---

类型二：查找问题

算法	思想	时间复杂度
二分查找	每次缩小一半范围	O(log n)
快速选择	分区后确定查找范围	O(n)

---

类型三：计算问题

问题	思想	时间复杂度
大整数乘法	Karatsuba 算法	O(n^1.585)
矩阵乘法	Strassen 算法	O(n^2.807)
最近点对	分区域计算	O(n log n)

---

类型四：树/图问题

问题	思想	应用
树的遍历	递归处理子树	二叉树问题
线段树	分区间存储	区间查询/更新
树状数组	分块存储	前缀和问题

---

6.2 按分治策略分类

策略	说明	示例
二分法	将问题分成两半	二分查找、归并排序
多分法	将问题分成多份	快速排序（多分）、Strassen
递归分解	递归处理子问题	树的遍历、表达式求值
合并统计	合并时统计信息	逆序对、区间统计

---

七、常见面试题总结

7.1 必须掌握的面试题

题目	难度	类型
Pow(x, n)	中等	快速幂
多数元素	简单	分治/投票
计算右侧小于当前元素的个数	困难	归并变形
数组中的第 K 个最大元素	中等	快速选择
为运算表达式设计优先级	中等	分治递归
合并 K 个升序链表	困难	分治合并
搜索二维矩阵 II	中等	二分查找
不同的二叉搜索树 II	中等	分治构造
漂亮数组	中等	分治构造
最大子数组和（分治版）	中等	分治统计

---

7.2 面试回答要点

Q：什么是分治算法？

分治算法是一种将复杂问题分解为若干个相同或相似的子问题，递归地解决这些子问题，然后将子问题的解合并成原问题的解的算法设计思想。核心步骤是：分（Divide）、治（Conquer）、合（Combine）。

Q：分治算法和动态规划的区别？

• 分治：子问题相互独立，可能重复计算
• 动态规划：子问题相互重叠，使用记忆化避免重复计算

Q：分治算法的适用条件？

1. 问题可以分解为相同类型的子问题
2. 子问题相互独立
3. 子问题的解可以合并
4. 有终止条件（子问题足够小）

Q：常见的时间复杂度？

• 二分查找：O(log n)
• 归并排序、快速排序：O(n log n)
• 快速选择：O(n)

---

八、总结

8.1 分治算法核心要点

要点	内容
核心思想	分而治之：分解 → 解决 → 合并
关键条件	问题可分解、子问题独立、可合并、有终止条件
经典算法	归并排序、快速排序、二分查找、快速选择
时间复杂度	通常 O(n log n) 或 O(log n)
空间复杂度	通常 O(log n) 或 O(n)

8.2 分治算法决策树

遇到问题
    │
    ├── 问题是否可以分解为相同类型的子问题？
    │   ├── 否 → 考虑其他算法
    │   └── 是 → 继续
    │
    ├── 子问题是否相互独立？
    │   ├── 否 → 考虑动态规划
    │   └── 是 → 继续
    │
    ├── 子问题的解是否可以合并？
    │   ├── 否 → 考虑其他算法
    │   └── 是 → 继续
    │
    └── 使用分治算法 ✅

8.3 学习建议

1. 理解核心思想：分 → 治 → 合
2. 掌握经典算法：归并排序、快速排序、二分查找
3. 学会分析复杂度：使用主定理
4. 对比学习：与递归、动态规划对比
5. 多做练习：分治题目套路明显，多练就能掌握

分治算法是算法面试中的重点，虽然实现可能较复杂，但思路清晰，掌握后能解决很多复杂问题！