【算法案例】分而治之算法（Divide and Conquer）搜索距离最近的两点
距离最近的两点（Closest Pairs of Points）是计算几何中的一个著名问题：给定一组平面坐标，找出该组坐标里面距离最近的两个点。如下图中所示，红色两点是所有坐标点中距离最近的一对。 该图片来自维基百科 - Closest pairs of points problem. 最简单直接的解决方法是暴力破解（Brutal Force），也就是计算所有两点之间的距离，然后找到最小值。但是这种方法需要的计算时间随着坐标位置的增加会呈指数级别增长，所以暴力破解方法的时间复杂度是 O(n2)。 一个更好的解决办法是采用分而治之算法（Divide and Conquer）。也就是先用二分法递归计算出各点之间的距离，然后逐一合并找出最小的那一个距离。这个算法的时间复杂度是 O(nlog2n) 。但是这里面有一个地方需要做特殊处理，我们一起来看看具体算法： 注：该图片来自网页 - Closest Pair: A Divide-and-Conquer Approach 算法思路： 把所有的点集合 S 分为大致数量相等的两部分 S1和…