Search algorithm to find a point from a given X value I implement the following algorithm in order to find a point from a given X value in a sorted list with the same distance between each X values. Here's an example of my list content with a delta of 10:

(687;10)
(12;20)
(24;30)
(10125;40)
(0;50)
(111;60)
(-2;70)



The delta can be any float number;
The list can be up to 2.000.000pts so it needs to be as fast as possible;
I can't change the type of the points container (IPointList from ZedGraph).


Here's the code:

private ZedGraph.PointPair findPoint(ZedGraph.CurveItem curve, double x) 
{
    if (curve.NPts == 1)
        return curve.Points[0];

    // Look for the min and max value
    double min = curve.Points[0].X;
    double max = curve.Points[curve.NPts - 1].X;

    double delta = curve.Points[1].X - min;

    // Prevent error if mouse is out of bounds.
    if (x &gt; max)
        x = curve.Points[curve.NPts - 1].X;
    else if (x &lt; min)
        x = curve.Points[0].X;

    double index = (x - min) / delta;
    int nearestIndex = (int)Math.Round(index, 0);

    if (nearestIndex &lt; curve.NPts)
    {
        return curve.Points[nearestIndex];
    }
    return curve.Points[curve.NPts - 1];
}
The NPts == 1 case shouldn't need to be handled separately.  The min-max clamping should take care of it, if you write it smartly (using &lt;= and &gt;= tests).

The min-max clamping should should do a short-circuit return.

Once clamped, there shouldn't be any need to test if (nearestIndex &lt; curve.NPts).

I would prefer to calculate the delta based on the min and max, for better precision.  Extrapolating based on Points[1].X - Points[0].X could let floating-point inaccuracies accumulate.

A sanity check before returning the value might be a good idea — it's up to you depending on how much you trust the data.

private ZedGraph.PointPair findPoint(ZedGraph.CurveItem curve, double x) 
{
    // Look for the min and max value
    double min = curve.Points[0].X;
    double max = curve.Points[curve.NPts - 1].X;

    // Prevent error if mouse is out of bounds.
    if (x &lt;= min) return curve.Points[0];
    if (x &gt;= max) return curve.Points[curve.NPts - 1];

    double delta = (max - min) / (curve.NPts - 1);
    int index = (int)Math.round((x - min) / delta, 0);

    Debug.Assert(Math.Abs(x - curve.Points[index].X) &lt;= delta / 2, "Interpolation error");
    return curve.Points[index];
}