c# - 使用 BinarySearch 通过差异查找最接近的索引

标签 c# optimization binary-search

我有一个包含大约 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 中所做的一切都低于我认为通过出色的二分搜索可以实现的目标。感谢您的输入。

最佳答案

只需进行二分查找,如果结果是否定的,您就会找到它要插入的位置并查看下一个和上一个条目 - 换句话说,使用您当前的代码,检查 indexindex - 1(在检查 index 不是 0 之后:)。找出哪个更近,您就完成了。

关于c# - 使用 BinarySearch 通过差异查找最接近的索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4306094/

相关文章:

c# - 生成 IL 以减少 for 循环中的计数器

c# - 使用 C# 中的 BitConverter 类将字节数组转换为十六进制值?

c++ - 如何提高内联函数效率?

c# - LINQ 可以在集合排序时使用二分查找吗?

c - 如何跟踪二分搜索算法中的最后一个索引?

c# - ORM/持久层建议

C#: "(subtype)data"和 "data as subtype"类型转换之间有什么区别吗?

c - 从文件读取到字符数组,C

python - 从 CSV 进行 Tensorflow 深度学习...梯度问题

c++ - 递归 divide et impera 二进制搜索中的错误