get next available integer using LINQ

I see a lot of answers that write a custom extension method, but it is possible to solve this problem with the standard linq extension methods and the static Enumerable class:

List<int> myInts = new List<int>() {1,2,3,5,8,13,21};

// This will set firstAvailable to 4.
int firstAvailable = Enumerable.Range(1, Int32.MaxValue).Except(myInts).First();

The answer provided by @Kevin has a undesirable performance profile. The logic will access the source sequence numerous times: once for the .Count call, once for the .FirstOrDefault call, and once for each .Contains call. If the IEnumerable<int> instance is a deferred sequence, such as the result of a .Select call, this will cause at least 2 calculations of the sequence, along with once for each number. Even if you pass a list to the method, it will potentially go through the entire list for each checked number. Imagine running it on the sequence { 1, 1000000 } and you can see how it would not perform well.

LINQ strives to iterate source sequences no more than once. This is possible in general and can have a big impact on the performance of your code. Below is an extension method which will iterate the sequence exactly once. It does so by looking for the difference between each successive pair, then adds 1 to the first lower number which is more than 1 away from the next number:

public static int? FirstMissing(this IEnumerable<int> numbers)
{
    int? priorNumber = null;

    foreach(var number in numbers.OrderBy(n => n))
    {
        var difference = number - priorNumber;

        if(difference != null && difference > 1)
        {
            return priorNumber + 1;
        }

        priorNumber = number;
    }

    return priorNumber == null ? (int?) null : priorNumber + 1;
}

Since this extension method can be called on any arbitrary sequence of integers, we make sure to order them before we iterate. We then calculate the difference between the current number and the prior number. If this is the first number in the list, priorNumber will be null and thus difference will be null. If this is not the first number in the list, we check to see if the difference from the prior number is exactly 1. If not, we know there is a gap and we can add 1 to the prior number.

You can adjust the return statement to handle sequences with 0 or 1 items as you see fit; I chose to return null for empty sequences and n + 1 for the sequence { n }.

This will be fairly efficient:

static int Next(this IEnumerable<int> source)
{
    int? last = null;
    foreach (var next in source.OrderBy(_ => _))
    {
        if (last.HasValue && last.Value + 1 != next)
        {
            return last.Value + 1;
        }

        last = next;
    }

    return last.HasValue ? last.Value + 1 : Int32.MaxValue;
}