Binary Search versus LINQ select statement

Question

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

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;
    }

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.

Answer 1

LINQ will not be more efficient than a binary search.

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

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