文章目录
  1. 最近点问题
  2. 选择问题

分治算法由两部分组成：(1)分：递归解决较小规模的问题；(2)治：由子问题的解构建原问题的解；一般来说，一个问题至少要分成两个子问题，算法才算分支算法；

最近点问题

对平面上一列点，找出欧式距离最短的一对点；直观的做法是检查所有的点对，但这样需花费O(N*N)的时间；下面介绍一种使用分治算法的解决方案。

不妨设这些点已按照X坐标排序，还有一个按照Y坐标排序的副本；

根据X坐标可以将这些点分成数目最多差一的两部分，记为P_L与P_R，并在中间设置一条分割线L;

那么点对可以分成三个部分：都在P_L中、都在P_R中、分别在P_L与P_R中；

对于前两部分点对中欧式距离最小者，可递归解决，那么要处理的问题就是分别在P_L与P_R中的点对欧式距离最小者；

考虑先得到两个子问题的解，记这两个解的最小值为d；显然，只需要考虑距分割线d以内的点组成的点对即可！

按照Y坐标由小到大依次考察P_L中距分割线d以内的点，考察P_R中那些Y坐标大于它且相差不超过d的点与它的距离，一直保留最小值及其对应点对。

选择问题

选择问题指找出有N个元素的表S中第k个最小的元素。介绍平均时间为O(N)的算法——快速选择。

  • 若S中只有一个元素，则k必为1，将S中的元素返回即可；
  • 否则，选择一个枢纽元v；
  • 将集合S-{v}分割为S_1与S_2；
  • 若$k\leq |S_{1}|$则第k个最小元素必在$S_{1}$中，接下来quicksearch(S_1, k)；若$k=|S_{1}|+1$则枢纽元就是第k个最小元素；若k大于$|S_{1}|+1$则第k个最小元素必在$S_{2}$中，接下来quicksearch(S_2, k-$|S_{1}|$-1)。