LINQ query binary search output

Question

I have a list of floating point data in which I want to find the index just below the value passed. 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

It is assumed that interpolation will be performed using xand ywith lowerIndexand lowerIndex+1.

The binary index lookup 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;
    }

Is there a more efficient way to do this with LINQ? Will it usually be faster? The comparison operation at the end of the do..while loop is the “hottest” line of code in my program.

Answer 1

LINQ will not be more efficient than binary search.

However, you are reinventing the existing method Array.BinarySearch.

, Array.BinarySearch (~ operator) , .

Answer 2

Linq IEnumerable. . , , , , (, LINQ).