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

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）。