Efficient way to get first missing element in ordered sequence?

Question

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?

Answer 1

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:

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

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

3. Subtract the current set of registers.

4. Pick the lowest.

Answer 2

I'd probably look at something like below; the Where can be done outside (as can the selector to be honest):

If you expect to start at 1:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable,
    Func<T, int> selectFunc)
{
    int expected = 1;
    foreach (T item in enumerable) {
        if (selectFunc(item) != expected) return expected;
        expected++;
    }
    return expected;
}

To start with the first item in the list:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable,
    Func<T, int> selectFunc)
{
    bool first = true;
    int prev = -1;
    foreach (T item in enumerable)
    {
        int val = selectFunc(item);
        if(first) {
            prev = val;
            first = false;
        } else if (val != prev + 1) {
            return prev + 1;
        }
        prev = val;
    }
    return first ? 1 : prev + 1;
}

It isn't clear how you wanted to handle nulls, so I didn't. Note that this only iterates once, and doesn't buffer everything.