Find Item With Max Value Less Than Another Value

I have an objec开发者_如何转开发t with two doubles:

class SurveyData(){ double md; double tvd; }

I have a list of these values that is already sorted ascending. I would like to find and return the index of the object in the list with the maximum tvd value that is less than or equal to a double. How can I efficiently accomplish this task?

Assuming you've got LINQ and are happy to use TakeUntil from MoreLINQ, I suspect you want:

var maxCappedValue = values.TakeUntil(data => data.Tvd >= limit)
                           .LastOrDefault();

That will get you the first actual value rather than the index, but you could always do:

var maxCappedPair = values.Select((value, index) => new { value, index })
                           .TakeUntil(pair => pair.value.Tvd >= limit)
                           .LastOrDefault();

for the index/value pair. In both cases the result would be null if all values were above the limit.

Of course, it would be more efficient to use a binary search - but also slightly more complicated. You could create a "dummy" value with the limit TVD, then use List<T>.BinarySearch(dummy, comparer) where comparer would be an implementation of IComparer<SurveyData> which compared by TVD. You'd then need to check whether the return value was non-negative (exact match found) or negative (exact match not found, return value is complement of where it would be inserted).

The difference in complexity is between O(n) for the simple scan, or O(log n) for the binary search. Without knowing how big your list is (or how important performance is), it's hard to advise whether the extra implementation complexity of the binary search would be worth it.

First filter by the objects that are less than or equal to the filter value (Where), and then select the maximum of those objects' values.

Since it's already in ascending order, just iterate through the set until you find a value greater than the filter value, then return the previous index.

Here's a way to do it with Linq:

int indexOfMax =
    data.Select((d, i) => new { Data = d, Index = i }) // associate an index with each item
        .Where(item => item.Data.tvd <= maxValue) // filter values greater than maxValue
        .Aggregate( // Compute the max
            new { MaxValue = double.MinValue, Index = -1 },
            (acc, item) => item.Data.tvd <= acc.MaxValue ? acc : new { MaxValue = item.Data.tvd, Index = item.Index },
            acc => acc.Index);

But in a case like this, Linq is probably not the best option... a simple loop would be much clearer.