定义

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解，可以理解成一种分目标完成程序的算法。二分法很多时候，就是一种分治的思想。
分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。顾名思义，分而治之。一般分为以下三个过程：

  • 分解：将原问题分解成一系列子问题。
  • 解决：递归求解各个子问题，若子问题足够小，则直接求解。
  • 合并：将子问题的结果合并成原问题。

    demo1:最大子数组和

    2022-04-28_222132.png
    分治： ```javascript function Status(l, r, m, i) { this.lSum = l; this.rSum = r; this.mSum = m; this.iSum = i; }

const pushUp = (l, r) => { const iSum = l.iSum + r.iSum; const lSum = Math.max(l.lSum, l.iSum + r.lSum); const rSum = Math.max(r.rSum, r.iSum + l.rSum); const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum); return new Status(lSum, rSum, mSum, iSum); }

const getInfo = (a, l, r) => { if (l === r) { return new Status(a[l], a[l], a[l], a[l]); } const m = (l + r) >> 1; const lSub = getInfo(a, l, m); const rSub = getInfo(a, m + 1, r); return pushUp(lSub, rSub); }

var maxSubArray = function(nums) { return getInfo(nums, 0, nums.length - 1).mSum; };

  1. 动态规划解法，更易理解
  2. ```javascript
  3. var maxSubArray = function(nums) {
  4.     let pre = 0, maxAns = nums[0];
  5.     nums.forEach((x) => {
  6.         pre = Math.max(pre + x, x);
  7.         maxAns = Math.max(maxAns, pre);
  8.     });
  9.     return maxAns;
  10. };

demo2：寻找两个正序数组的中位数

2022-04-29_212708.png

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number[]} nums2
  4.  * @return {number}
  5.  */
  6. var findMedianSortedArrays = function (nums1, nums2) {
  7.     const length1 = nums1.length;
  8.     const length2 = nums2.length;
  9.     const sumLenx = length1 + length2;
  10.     /** 存储的值表示中位数前面有几个数. */
  11.     const targetMap = [];
  12.     const result = [];
  13.     /** 中位数的确定因奇偶性的不同, 计算的方式也不一样. */
  14.     if (sumLenx % 2 === 0) {
  15.         targetMap.push((sumLenx >> 1) - 1, sumLenx >> 1);
  16.     } else {
  17.         targetMap.push(sumLenx >> 1);
  18.     }
  19.     const targetMapLen = targetMap.length;
  20.     /** 两个数组若均为空值则直接返回0. */
  21.     if (!length1 && !length2) {
  22.         return 0;
  23.     }
  24.     /** 两个数组若存在一个数组为空数组而另一个数组为非空数组则直接计算返回. */
  25.     if (!length1 || !length2) {
  26.         const targetNums = !length1 ? nums2 : nums1;
  27.         if (targetMapLen % 2 === 0) {
  28.             return (targetNums[targetMap[0]] + targetNums[targetMap[1]]) / 2;
  29.         }
  30.         return targetNums[targetMap[0]];
  31.     }
  32.     /** 二分查询满足 target >= array[index] 的最远坐标. */
  33.     const divideHight = (start, end, array, target) => {
  34.         let mid = (start + end) >> 1;
  35.         if (start > end - 1) {
  36.             if (array[start] > target) {
  37.                 return start;
  38.             }
  39.             return start + 1;
  40.         }
  41.         if (array[mid] > target) {
  42.             return divideHight(start, mid, array, target);
  43.         } else {
  44.             return divideHight(mid + 1, end, array, target);
  45.         }
  46.     }
  47.     /** 二分查询满足 target <= array[index] 的最近坐标. */
  48.     const divideLow = (start, end, array, target) => {
  49.         let mid = (start + end) >> 1;
  50.         if (start >= end - 1) {
  51.             if (array[start] < target) {
  52.                 return end;
  53.             }
  54.             return start;
  55.         }
  56.         if (array[mid] >= target) {
  57.             return divideLow(start, mid, array, target);
  58.         } else {
  59.             return divideLow(mid, end, array, target);
  60.         }
  61.     }
  62.     /** 二分其中数组, 在另一个数组中查询当前值是否为中位数其中之一. */
  63.     const divideMain = (l1, l2, length, targetArr, curArr, target) => {
  64.         while (l1 <= l2) {
  65.             /** 坐标可看作当前数组中有多少个数小于当前值 */
  66.             const mid = (l1 + l2) >> 1;
  67.             const index = divideHight(0, length - 1, targetArr, curArr[mid]);
  68.             const lowIndex = divideLow(0, length - 1, targetArr, curArr[mid]);
  69.             /** 
  70.                 当前坐标 + 查询到的坐标(最远坐标) => 有多少个数小于目标值.
  71.                 注意:
  72.                     这里需要额外计算与目标值相同的最近坐标
  73.                       nums1: [1, 1, 2, 2] 
  74.                       nums2: [1, 1, 2, 2]
  75.                     对于上面 nums1[2] 这个数组计算出来的可用索引是 2(最近)、4(最远). 
  76.                     若没有处理最近坐标则2这个值一直无符合要求, 导致计算中位数出错.
  77.             */
  78.             if (mid + index === target || nums1[mid] === nums2[index - 1] && targetArr[index - 1] === targetArr[lowIndex] && mid + index >= target && mid + lowIndex <= target) {
  79.                 result.push(curArr[mid]);
  80.                 return true;
  81.             } else if (mid + index > target) {
  82.                 l2 = mid - 1;
  83.             } else {
  84.                 l1 = mid + 1;
  85.             }
  86.         }
  87.         return false;
  88.     }
  89.     for (let i = 0; i < targetMapLen; ++i) {
  90.         const target = targetMap[i];
  91.         if (divideMain(0, length1 - 1, length2, nums2, nums1, target)) {
  92.             continue;
  93.         }
  94.         divideMain(0, length2 - 1, length1, nums1, nums2, target);
  95.     }
  96.     /** 若所有值均相同 */
  97.     if (result.length === 0 || sumLenx === 2 && nums1[0] === nums2[0]) {
  98.         return nums1[0] ?? nums2[0];
  99.     }
  100.     /** 偶数计算 */
  101.     if (targetMapLen % 2 === 0) {
  102.         return (result[0] + result[1]) / 2;
  103.     }
  104.     /** 奇数计算 */
  105.     return result[0];
  106. };