通过与BinarySearch的差异查找最接近的索引

Question

我有一个大约500,000英特的排序数组.目前我通过获取目标int和所有元素之间的差异,然后使用LINQ(非常低效)按最小差异排序来选择正确的索引.

我希望能够做一些与BinarySearch非常相似的事情.

鉴于:

Pos Value
0   10
1   20
2   30
4   50
5   60

如果我想找到值24的最接近的值,我希望返回的索引为1.

鉴于:

int index = myArray.BinarySearch(values, 24);
if (index < 0)
    index = ~index;

这返回2,因为它给出了下一个元素,而不是最接近的元素.是否可以编写一个返回最接近索引的IComparer？

给定值:

Value ExpectedReturn
20    1
24    1
25    2
26    2
30    2

我想尽快做到这一点.到目前为止,我在LINQ中所做的一切都与我认为可以通过完善的二进制搜索实现的目标相提并论.谢谢你的反馈.

Answer 1

只做二进制搜索,如果结果为负,你就可以找到它的插入位置,然后查看下一个和上一个条目 - 换句话说,使用当前代码,检查index并且index - 1(在检查后index不是0 :) .找出哪个更接近,你就完成了.