博客

详解分治算法原理与使用方法

分治算法

概述

分治算法是一种将问题分解成若干个子问题，再将子问题分解成更小的子问题，直到问题规模可以简单解决的算法。当所有的子问题解决了，原问题的解就是这些子问题解的合并。

分治算法一般采用递归思想，分解问题过程中需要满足三个条件：
1. 原问题可以分解成若干个子问题；
2. 子问题具有相同的解法；
3. 子问题规模减小到一定程度时可以直接求解。

示例 1：归并排序

归并排序是一种经典的分治算法。将待排序序列分成若干个小序列，每个小序列都是有序的。然后将这些小序列合并，最终得到一个有序的序列。

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

上述代码中，mergeSort()函数实现了将待排序数组分解成若干个子问题（取中间的元素进行分割），直至子问题规模减小至一定程度（当数组长度小于等于1时终止递归）。merge()函数实现了将有序的子序列合并成一个完整的有序数组。

示例 2：二分查找

二分查找是一种典型的分治算法。基于前提条件，即在使用二分查找之前，需要对数据进行排序，将数据转换成由小到大排列的有序数组。

在有序数组中，先将待查找范围的左、右两端指针分别指向左右两端，然后计算左右两端指针的中间位置指针mid，将此处值与待查项进行比较，若相等，则查找成功；若不相等，则根据比较结果，将查找范围缩小至[mid+1, 右]或[左，mid-1]，继续查找。

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

上述代码中，binarySearch()函数实现了将有序数组分解成若干个子问题，直至子问题规模减小至一定程度。每次查找时取查找范围的中间位置指针mid进行比较，根据比较结果缩小查找范围。

Tags: