代码之家 › 专栏 › 技术社区 › jsmith

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

binary-search optimization c#

jsmith · 技术社区 · 14 年前

我有一个大约500000个整数的排序数组。目前,我正在选择正确的索引,方法是获取目标int和所有元素之间的差异,然后使用linq(非常低效)按最小差异排序。

我想能够做一些非常类似的双晶搜索。

鉴于:

如果我想为值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中所做的一切都低于我认为通过一个完善的二进制搜索可以达到的水平。感谢您的意见。

2 回复 | 直到 11 年前

Jon Skeet 14 年前

只需进行二进制搜索,如果结果是负数,那么就可以找到插入的位置并查看下一个 和以前 输入-换句话说,使用当前代码,检查 index 和 index - 1 (检查之后 指数 不是0:)。找出哪个更接近,你就完了。

omer schleifer 11 年前

下面是一个简短的演示,基于约翰·斯基特的解释。此方法只返回介于“时间”和“时间”之间的日期。当然,它假定原始数组是按时间排序的。

private DateTime[] GetDataForEntityInInterval(DateTime fromTime, DateTime toTime)
        {

        DateTime[] allValues = GetAllValuesFromDB();
        int indexFrom = Array.BinarySearch(allValues, fromTime);

         if(indexFrom < 0)
         {
             int indexOfNearest = ~indexFrom;

             if (indexOfNearest == allValues.Length)
             {
                 //from time is larger than all elements
                 return null;
             }
             else if (indexOfNearest == 0)
             {
                 // from time is less than first item
                 indexFrom = 0;
             }
             else
             {
                 // from time is between (indexOfNearest - 1) and indexOfNearest
                 indexFrom = indexOfNearest;
             }
         }

         int indexTo = Array.BinarySearch(allValues, toTime);
         if (indexTo < 0)
         {
             int indexOfNearest = ~indexTo;

             if (indexOfNearest == allValues.Length)
             {
                 //to time is larger than all elements
                 indexTo = allValues.Length - 1;
             }
             else if (indexOfNearest == 0)
             {
                 // to time is less than first item
                 return null;
             }
             else
             {
                 // to time is between (indexOfNearest - 1) and indexOfNearest
                 indexTo = Math.Max(0, indexOfNearest - 1);
             }
         }

        int length = indexTo - indexFrom + 1;
        DateTime[] result = new DateTime[length];
        if (length > 0)
        {
            Array.Copy(allValues, indexFrom, result, 0, length);
        }
        return result;

    }