基于距离查询3D空间目标点的最小步数优化方案问询

当前代码无法稳定工作的核心问题在于：

• 仅比较middle、low、high三点的距离就决定搜索方向，忽略了距离函数的单调性特性——对于X轴上的点，到目标点的距离是一个先递减后递增的凸函数，而非单调函数，直接用当前的二分逻辑会错过真正的最小值点。
• 终止条件不明确，当搜索区间缩小到相邻点时，无法正确判断哪个点距离更近。

修复后的X轴二分查找函数 #

const findClosestX = (low, high, destinationPoint) => {
  // 当区间缩小到两个点时，直接返回距离更近的那个
  if (high - low <= 1) {
    const distLow = new Point(low, 0, 0).getDistance(destinationPoint);
    const distHigh = new Point(high, 0, 0).getDistance(destinationPoint);
    return distLow <= distHigh ? low : high;
  }

  const mid = Math.floor((low + high) / 2);
  const midDist = new Point(mid, 0, 0).getDistance(destinationPoint);
  const midNextDist = new Point(mid + 1, 0, 0).getDistance(destinationPoint);

  // 根据凸函数特性判断最小值所在区间：
  // 如果mid的距离大于mid+1，说明最小值在右侧；否则在左侧
  if (midDist > midNextDist) {
    return findClosestX(mid + 1, high, destinationPoint);
  } else {
    return findClosestX(low, mid, destinationPoint);
  }
};

关键改进点 #

• 利用凸函数特性：X轴上点到目标点的距离函数是凸函数，最小值点左侧距离递减，右侧递增。通过比较mid和mid+1的距离，能准确判断最小值所在区间。
• 明确终止条件：当区间只剩两个点时，直接比较两者距离返回更近的点，避免逻辑错误。
• 扩展到3D空间：要定位完整的3D目标点，需分别对X、Y、Z轴执行上述二分查找，最终组合得到距离目标点最近的整数坐标点，整体复杂度降为O(log n)（每个轴一次二分）。

完整3D定位示例 #

const findClosestPoint = (destinationPoint) => {
  const x = findClosestX(0, 100, destinationPoint);
  // 同理实现findClosestY和findClosestZ函数
  const y = findClosestY(0, 100, destinationPoint);
  const z = findClosestZ(0, 100, destinationPoint);
  return new Point(x, y, z);
};

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