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

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

double delta = curve.Points.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.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];
}

• Ugh, IPointList doesn't implement IEnumerable<PointPair> or even IEnumerable. I assume you can't just add that to IPointList? – svick Dec 22 '14 at 19:28

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.X - Points.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.X;
double max = curve.Points[curve.NPts - 1].X;

// Prevent error if mouse is out of bounds.
if (x <= min) return curve.Points;
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];
}