Quickest way to find position of item less than or equal to double in sorted list C# -

i exploring fastest way iterate through 3 sorted lists find position of first item equal or less double value. lists contains 2 columns of doubles.

i have 2 following working examples attached below, these encompassed bigger while loop (which modifies currentpressure list changing [0] value) value. but, considering amount of rows (500,000+) being parsed bigger while loop, code below slow (one iteration of 3 while loops takes >20 ms).

"allpressures" contains rows while currentpressure modified remaining code. while loops used align time flow, rpm , position lists time in pressure list.

in other words trying find quickest way determine x of instance

flowlist[x].time =< currentpressure[0].time 

any suggestions appreciated!

examples:

           (int = 0; < allpressures.count; i++)             {                 if (flowlist[i].time >= currentpressure[0].time)                 {                     fl = i;                     break;                 }             }              (int = 0; < allpressures.count; i++)             {                 if (rpmlist[i].time >= currentpressure[0].time)                 {                     rp = i;                     break;                 }             }              (int = 0; < allpressures.count; i++)             {                 if (positionlist[i].time >= currentpressure[0].time)                 {                     bp = i;                     break;                 }             } 

using while loop:

            while (flowlist[fl].time < currentpressure[0].time)             {                 fl++;             }              while (rpmlist[rp].time < currentpressure[0].time)             {                 rp++;             }              while (positionlist[bp].time < currentpressure[0].time)             {                 bp++;             }   

the problem doing linear search. means in worst case scenario iterating on elements in lists. gives computational complexity of o(3*n) n length of lists , 3 number of lists searching.

since lists sorted can use faster binary search has complexity of o(log(n)) , in case o(3*log(n)).

luckily don't have implement yourself, because .net offers helper method list.binarysearch(). need 1 takes custom comparer, because want compare pressuredata objects.

since looking index of closest value that's less search value, you'll have use little trick: when binarysearch() doesn't find matching value returns index of next element larger search value. it's easy find previous element smaller search value.

here extension method implements this:

public static int findmaxindex<t>(     list<t> sortedlist, t inclusiveupperbound, icomparer<t> comparer = null) {     var index = sortedlist.binarysearch(inclusiveupperbound, comparer);      // max value found in list. return index.     if (index >= 0)         return index;      // max value not found , "~index" index of     // next value greater search value.     index = ~index;      // there values in list less search value.     // return index of closest one.     if (index > 0)         return index - 1;      // values in list greater search value.     return -1; } 

test @ https://dotnetfiddle.net/klzsm5

use method comparer understands pressuredata objects:

var pdc = comparer<pressuredata>.create((x, y) => x.time.compareto(y.time)); var fl = flowlist.findmaxindex(currentpressure[0], pdc); 

here working example: https://dotnetfiddle.net/dmgzsv