Efficient way to get first missing element in ordered sequence?

c#, linq, linq-to-sql, search

Solution

Edit: I just noticed that `enumerable` is `IQueryable<T>` but `selectFunc` and `whereFunc` are of type `Func<T, _>`. This will cause the `Enumerable` versions of `OrderBy` and `Where` to be called, rather than using database calls. You probably want to switch them to `Expression<Func<T, _>>` instead.

If you don't want to order `regNums` first, here's a O(n) golf-style solution:

var max = regNums.Max(i => (int?)i) ?? 0;
return Enumerable.Range(1, max + 1)
                 .Except(regNums)
                 .Min();

By line:

By casting to `int?`, `Max` will return `null` if `regNums` is empty, coalesced to `0`.

Build a sequence of all possible registers, including our next value if full.

Subtract the current set of registers.

Pick the lowest.

Problem

I have an ordered sequence like {1, 3, 5, 6, 8, 9} I want to get first missing element(2 in the example) or max() if sequence contains no missing elements. Now I'm doing it like this: ``` public static int GetRegisterNumber<T>(this IQueryable<T> enumerable, Func<T, bool> whereFunc, Func<T, int?> selectFunc) { var regNums = enumerable.OrderBy(selectFunc).Where(whereFunc).ToArray(); if (regNums.Count() == 0) { return 1; } for (int i = 0; i < regNums.Count(); i++) { if (i + 1 != regNums[i]) { return regNums[i].Value + 1; } } return regNums.Last().Value + 1; } ``` But i think there are much faster methods. Any suggestions?

Original source