CLRS最近点对分治算法点集拆分逻辑错误排查求助

你的拆分逻辑存在两处核心错误，是导致结果不符合预期的直接原因：

理解偏差 #

• X_L和Y_L必须对应完全相同的点集合，仅排序规则不同（X_L按x升序，Y_L按y升序），X_R和Y_R同理。你只保证了两组数组的数量接近，没有保证点集合一致，这是最根本的问题。
• 竖分割线的位置由按x排序的X数组中点决定，不是和排序无关，所有点的归属都要和分割线的位置匹配。

代码错误 #

1. 中位数计算逻辑错误 #

处理奇数个点的代码存在越界风险：

else {
    mid = mid + 1;
    median = xs[mid + 1];   
}

当num_p=3时，初始mid=1，执行后mid=2，访问xs[3]会直接越界。正确的分割线取值可以直接取X数组中点的x坐标：

mid = num_p / 2;
int split_x = xs[mid].x;

2. Y数组拆分逻辑完全错误 #

你当前拆分Y数组的逻辑是按遍历顺序计数填充，完全没有判断点的归属，甚至在y_li == mid时将同一个点同时加入左右数组，导致Y_L和X_L的点集合完全不匹配，分治计算左右最小距离时点集和预期不符，结果自然出错。
正确的Y数组拆分逻辑：遍历按y排序的ys数组，对每个点判断它属于左半部分还是右半部分，对应加入Y_L或Y_R，归属判断规则必须和X数组拆分时完全一致：

• 点x < split_x → 加入Y_L
• 点x > split_x → 加入Y_R
• 点x == split_x → 进一步判断该点是否属于X的前mid个点，是则加入Y_L，否则加入Y_R

这样就能保证Y_L和X_L的点集合完全一致，仅排序顺序不同。

内容的提问来源于stack exchange，提问作者TheYellowBlueWhite