Search algorithm to find a point from a given X value

Question

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 > max)
        x = curve.Points[curve.NPts - 1].X;
    else if (x < min)
        x = curve.Points[0].X;

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

    if (nearestIndex < curve.NPts)
    {
        return curve.Points[nearestIndex];
    }
    return curve.Points[curve.NPts - 1];
}

Answer 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 <= and >= tests).

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

Once clamped, there shouldn't be any need to test if (nearestIndex < 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 <= min) return curve.Points[0];
    if (x >= 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) <= delta / 2, "Interpolation error");
    return curve.Points[index];
}