二进制搜索与LINQ select语句 [英] Binary Search versus LINQ select statement

问题描述

我有一个浮点数据列表，其中我想找到刚刚低于传递值的索引。一个简化的例子：

I have a list of floating point data in which I want to find the index just below a passed value. A simplified example:

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

目的是使用 使用 lowerIndex 和 lowerIndex + 1 / code>。

The intent is that an interpolation will then be performed with x and y using lowerIndex and lowerIndex+1.

二进制索引搜索算法类似于

The binary index search algorithm looks like

    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循环结束时的比较操作是我的程序中最热的代码行。

Is there a more efficient way to do this with LINQ? Would it typically be faster? The comparison operation at the end of the do..while loop is the "hottest" line of code my program.

推荐答案

LINQ

但是，您正在重新创建现有的 Array.BinarySearch 方法。

However, you are re-inventing the existing Array.BinarySearch method.

如果没有找到元素， Array.BinarySearch 将返回按位补码（〜 ）的位置应该是。

If the element is not found, Array.BinarySearch will return the bitwise complement (~ operator) of the location where it ought to be.

这篇关于二进制搜索与LINQ select语句的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！