二进制搜索与LINQ选择语句

Question

我有一个浮点数据列表,我想在其中找到传递值下方的索引.一个简化的例子:

double[] x= {1.0, 1.4, 2.3, 5.6, 7.8};
double[] y= {3.4, 8.2, 5.3, 8.1, 0.5};
int lowerIndex = BinaryIndexSearch(x, 2.0);  // should return 1

这样做的目的是插值将然后执行x并y使用lowerIndex和lowerIndex+1.

二进制索引搜索算法看起来像

    int BinaryIndexSearch(double[] x, double value)
    {
        int upper = x.Length - 1;
        int lower = 0;
        int pivot;

        do
        {
            pivot = (upper + lower) / 2;

            if (value >= x[pivot])
            {
                lower = pivot + 1;
            }
            else
            {
                upper = pivot - 1;
            }
        }
        while (value < x[pivot] || value >= x[pivot + 1]);

        return pivot;
    }

使用LINQ有更有效的方法吗？它通常会更快吗？do..while循环结束时的比较操作是我程序中"最热"的代码行.

Answer 1

LINQ不会比二进制搜索更有效.

但是,您正在重新发明现有Array.BinarySearch方法.

如果找不到该元素,Array.BinarySearch将返回~它应该位于的位置的按位补码(运算符).

Answer 2

Linq是通过IEnumerable编写的.它不是为了表现.作为一般经验法则,所有对所使用的数据结构有深入了解的算法将比通用解决方案(如LINQ)更快.