分治算法及其策略

分治（divide and conquer），全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。
1，分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止
2，治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。
“归并排序”是分治策略的典型应用之一。
1，分：递归地将原数组（原问题）划分为两个子数组（子问题），直到子数组只剩一个元素（最小子问题）。
2，治：从底至顶地将有序的子数组（子问题的解）进行合并，从而得到有序的原数组（原问题的解）。

一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。
1，问题可以分解：原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
2，子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
3，子问题的解可以合并：原问题的解通过合并子问题的解得来。
显然，归并排序满足以上三个判断依据。
1，问题可以分解：递归地将数组（原问题）划分为两个子数组（子问题）。
2，子问题是独立的：每个子数组都可以独立地进行排序（子问题可以独立进行求解）。
3，子问题的解可以合并：两个有序子数组（子问题的解）可以合并为一个有序数组（原问题的解）。
分治在算法和数据结构的设计中应用得非常广泛。分治是一种“润物细无声”的算法思想，隐含在各种算法与数据结构之中。
1，二分查找：二分查找是将有序数组从中点索引处分为两部分，然后根据目标值与中间元素值比较结果，决定排除哪一半区间，并在剩余区间执行相同的二分操作。
2，归并排序：上面已介绍，不再赘述。
3，快速排序：快速排序是选取一个基准值，然后把数组分为两个子数组，一个子数组的元素比基准值小，另一子数组的元素比基准值大，再对这两部分进行相同的划分操作，直至子数组只剩下一个元素。
4，桶排序：桶排序的基本思想是将数据分散到多个桶，然后对每个桶内的元素进行排序，最后将各个桶的元素依次取出，从而得到一个有序数组。
5,树：例如二叉搜索树、AVL 树、红黑树、B 树、B+ 树等，它们的查找、插入和删除等操作都可以视为分治策略的应用。
6,堆：堆是一种特殊的完全二叉树，其各种操作，如插入、删除和堆化，实际上都隐含了分治的思想。
7,哈希表：虽然哈希表并不直接应用分治，但某些哈希冲突解决方案间接应用了分治策略，例如，链式地址中的长链表会被转化为红黑树，以提升查询效率。
时间复杂度为 Ologn的搜索算法通常是基于分治策略实现的，例如二分查找和树。
1,问题可以分解：二分查找递归地将原问题（在数组中进行查找）分解为子问题（在数组的一半中进行查找），这是通过比较中间元素和目标元素来实现的。
2,子问题是独立的：在二分查找中，每轮只处理一个子问题，它不受其他子问题的影响。
3,子问题的解无须合并：二分查找旨在查找一个特定元素，因此不需要将子问题的解进行合并。当子问题得到解决时，原问题也会同时得到解决。

/* 二分查找：问题 f(i, j) */intdfs(int[]nums,inttarget,inti,intj){// 若区间为空，代表无目标元素，则返回 -1if(i>j){return-1;}// 计算中点索引 mintm=(i+j)/2;if(nums[m]<target){// 递归子问题 f(m+1, j)returndfs(nums,target,m+1,j);}elseif(nums[m]>target){// 递归子问题 f(i, m-1)returndfs(nums,target,i,m-1);}else{// 找到目标元素，返回其索引returnm;}}/* 二分查找 */intbinarySearch(int[]nums,inttarget){intn=nums.length;// 求解问题 f(0, n-1)returndfs(nums,target,0,n-1);}