本文转载自微信公众号“bigsai”，作者bigsai。转载本文请联系bigsai公众号。前言分治算法（divideandconquer）是常用的五种算法（分治算法、动态规划算法、贪心算法、回溯法、分治边界法）之一。很多人可能在平时的学习中只知道分治算法，但是对于分治算法可能没有系统的学习。本文将带你更全面地了解分治算法。在学习分治算法之前，我想问大家一个问题。相信每个人小时候都有过存钱罐的经历。父母亲戚给钱，就把钱存到自己的宝库里。我们会每隔一段时间数数数数钱。但是处理一堆钱你可能会觉得复杂，因为数据相对于大脑来说有点庞大，而且很容易出错。你可以先把它分成几个小部分，然后把它们加起来计算总数。这堆钱的总量当然是，如果你觉得每一部分的钱量还是太大了，你还是可以分而合之。我们之所以有这么多是因为：每一小堆钱的计算方式和最大一堆钱的计算方式是一样的（区别在于大小）而大堆钱的总和其实是一小堆钱的结果总和。这样一来，其实是有一种分而治之的思维。当然，钱都是想出来的……分治算法介绍分治算法是利用分治思想的算法。什么是分而治之？将问题分解为两个或多个相同或相似的子问题，再将子问题分解为更小的子问题……直到最后的子问题能够简单直接地求解，而原的解问题是子问题的解决方案的组合。在计算机科学中，分治法是一个非常重要的算法，它使用了分治思想。分而治之是许多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（fastFouriertransform）等。将父问题分解成子问题同理求解，很符合递归的概念，所以分治算法通常采用递归的方式实现（当然也有非递归的）实现）。分治算法的描述从字面上看也很容易理解。分而治之其实有一个合并的过程：Divide：递归解决更小的问题（停在终止层或者能解决的时候）Conquer：递归解决，如果问题小到可以直接解决。Combine：将子问题的解构造成父类问题。一般的分治算法在文中分解为两次或多次递归调用，子类问题一般不相交（互不影响）。当求解规模较大的问题时，直接求解是困难的，但当规模较小时，问题容易求解且满足分而治之算法的适用条件，则分而治之可以使用and-conquer算法。那么分治算法解决的问题应该满足什么条件（特征）呢？1.原来的问题通常太大而无法直接解决，但当问题缩小到一定程度时就可以轻松解决。2.问题可以分解成几个规模较小的子问题，用相同（相似）的方式解决。并且子问题的解是独立的，互不影响。3.将问题分解的子问题组合起来就可以得到问题的解。你可能想知道分而治之算法和递归有什么关系？其实分而治之重要的是一种思想，着眼于问题的分治、合并的过程。而递归是一种方法（工具）。这个方法通过方法调用自己形成一个来回过程，分而治之可能会多次使用这样的来回过程。分治算法经典问题对于分治算法的经典问题，最重要的是它的思想，因为我们大多数人都是用递归来实现的，所以大部分代码实现都很简单，并且本文也着重于这个想法。分治算法的经典问题，我个人把它分为两类：子问题完全独立和子问题不完全独立。1.子题完全独立，即原题的答案完全可以从子题的结果中推导出来。2.子问题不完全独立。对于一些区间型的问题或者跨区间的问题，使用分而治之可能会导致跨区间。在考虑问题的时候，你需要认真地向他们学习。二分查找二分查找是分而治之的一个例子，但是二分查找有其特殊性。序列的有序结果是一个值。NormalBinary将一个完整的区间分成两个区间。两个区间应该分别求值，然后确认结果，但是通过有序的区间，可以直接判断结果在哪个区间，所以只需要为两个区间计算其中一个区间，然后继续直到结束。有递归和非递归的实现方法，但使用的更多的是非递归的：publicintsearchInsert(int[]nums,inttarget){if(nums[0]>=target)return0;//剪枝if(nums[nums.length-1]==target)returnnums.length-1;//剪枝if(nums[nums.length-1]
