通过BinarySearch通过差异查找最接近的索引 [英] Find closest index by difference with BinarySearch

问题描述

我有大约500,000个整数的排序数组.目前，我正在通过选择目标int与所有元素之间的差异来选择正确的索引，然后使用LINQ(效率非常低)按最小差异进行排序.

I have a sorted array of about 500,000 ints. Currently I am selecting the correct index by taking the differences between my target int, and all of the elements, and then sorting by the minimum difference using LINQ (very inefficient).

我希望能够使用BinarySearch进行类似的操作.

I'd like to be able to do something very similar with BinarySearch.

给出:

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

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

If I want to find the closest value for value 24 I would want the index returned to be 1.

给出:

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

这将返回2，因为它给出了行中的下一个元素，而不是最接近的元素.是否可以编写一个IComparer来返回最接近的索引?

This returns 2 since it gives the next element in line, instead of the closest. Is it possible to write an IComparer that would return the closest index?

给出值:

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

我正在尝试使其尽可能快.到目前为止，我在LINQ中所做的一切都低于我认为可以通过完善的二进制搜索实现的功能.谢谢您的投入.

I am trying to make this as fast as possible. Everything I have done so far in LINQ has been sub par to what I think can be achieved with a well done binary search. Thank you for the input.

推荐答案

只进行二进制搜索，如果结果为负，则找到将其插入的位置，并查看下一个和上一个>条目-换句话说，使用您当前的代码，检查 index 和 index-1 (在检查 index 不是0之后:).找出更接近的位置，就可以完成.

Just do the binary search, and if the result is negative you then find where it would be inserted and look at the next and previous entry - in other words, with your current code, check index and index - 1 (after checking that index isn't 0 :). Find out which is closer, and you're done.

这篇关于通过BinarySearch通过差异查找最接近的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！