search - 排序整数列表中的近似搜索算法

Question

考虑一个整数数组（假设已排序）；我想以最快的方式找到最接近给定整数的整数的数组索引。在有多种可能性的情况下，算法应该识别所有可能性。

示例：考虑 T=(3, 5, 24, 65, 67, 87, 129, 147, 166)，如果给定的整数是 144，那么代码应该将 147 标识为最接近的整数，并给数组索引 7对应于该条目。对于 66 的情况，算法应该识别 65 和 67。

是否有 O(1) 或至少 O(log N) 算法来做到这一点？直接搜索算法（二分搜索、树搜索、散列等）实现将不起作用，因为它们需要完美匹配。有什么办法可以修改这些来处理近似搜索？

我正在开发一个 C 代码。

谢谢

Answer 1

进行二分搜索，直到找到一个元素。如果有匹配项，请沿着您的邻居查找其他匹配项。如果没有匹配项，请查看您的直接邻居以找到最接近的匹配项。

Answer 2

正确实施binary-search应该可以解决问题 - 只要您确定搜索范围减少到仅两个项目的时刻。然后，您只需选择最接近的一个。复杂度：O(log n)。