c# - 使用 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 之后:)。找出哪个更近，您就完成了。