我有一个包含大约 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 中所做的一切都低于我认为通过出色的二分搜索可以实现的目标。感谢您的输入。
最佳答案
只需进行二分查找,如果结果是否定的,您就会找到它要插入的位置并查看下一个和上一个条目 - 换句话说,使用您当前的代码,检查 index
和 index - 1
(在检查 index
不是 0 之后:)。找出哪个更近,您就完成了。
关于c# - 使用 BinarySearch 通过差异查找最接近的索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4306094/