# Fastest way to check data against an envelope

If I have two arrays containing max and min points which make up an envelope. It's quick to test if any point in a given data array goes outside of that envelope using:

 for (int i = 0; i < envMax.size(); i++)
{
if ((data[i] < envMin[i]) || (data[i] > envMax[i]))
{
return false;
}
}
return true;


However, my data array can be large and I have to load the max and min envelope data from a file for each new data array which needs testing (just the way the system works). So it might be quicker to just use a smaller number of points for the envelope and interpolate. But whats the quickest way of doing this with a reduced number of points. I can do (sudo code):

for each data point
find min and max envelope point before and after data point
calculate equation of line between two points
put in data "x" value
check resultant y value.


Alternatively I can just generate N max and min envelope points (where N is = length(data)) (same thing really)...

But this seems computational exhausting. I can't believe I am the first person to want to do this so is there an accepted (fastest) method / algorithm type?

EDIT:

The problem is essentially this: Check that the blue line is within the green lines. But doing it when the number of points describing the green lines is much less than the number of points describing the blue line.

• Searching for a value in a unsorted array is going to be O(n) lower bound. Nothing you can really do to help that other than doing a bit of preprocessing on the data (which will itself take O(n)). – ratchet freak May 25 '18 at 10:57
• Pseudocode doesn't derive from the unix command "sudo". – Yuval Filmus May 25 '18 at 11:47
• Ha, I'm dyslexic, I spell it how it sounds. :) – Tim Mottram May 25 '18 at 11:55
• @TimMottram I was once very confused by somebody talking about "persuade-o-code" until I realized he was making the opposite mistake to you -- pronouncing it like it's spelled. :-) – David Richerby May 25 '18 at 12:32