Get missing sequential numbers from array

Question

I have an array like Original = {1, 2, 3, 6, 7, 8, 9, 10, 12}. After removing some elements like Delete = {6, 7} from it, I want to get n sequential numbers which are not in the array, like IDs = {4, 5, 6, 7, 11, 13, 14, ..., n}.

After getting the numbers I want the original array to be changed to the updated array.

public static ushort GetNextID(ref List<ushort> Updating)
{
    for (var i = 0; i < Updating.Count; i++)
    {
        if (Updating[i] != i + 1)
        {
            Updating.Insert(i, Convert.ToUInt16(i + 1));
            return Convert.ToUInt16(i + 1);
        }
    }
    Updating.Add(Convert.ToUInt16(Updating.Last() + 1));
    return Convert.ToUInt16(Updating.Last() + 1);
}
public static ushort[] GetNextIDs(ref List<ushort> Updating, ushort Count)
{
    List<ushort> IDs = new List<ushort>();
    for (var t = 0; t < Count; t++) IDs.Add(GetNextID(ref Updating));
    return IDs.ToArray();
}
static void Main(string[] args)
{
    IEnumerable<ushort> Original = new ushort[] { 1, 2, 3, 4, 5, 6, 7, 9, 10 };
    IEnumerable<ushort> Delete = new ushort[] { 4, 5, 6 };
    var Updating = Original.Except(Delete).ToList();

    // Expected: 4, 5, 6, 8, 11, 12, 13, 14
    // Outputs:  4, 5, 6, 8, 12, 13, 14, 15
    foreach (var id in GetNextIDs(ref Updating, 8)) Console.WriteLine(id);

    Console.WriteLine();

    // 1, 2, 3, (4, 5, 6), 7, (8), 9, 10, (11, 12, 13, 14)
    foreach (var i in Updating) Console.WriteLine(i);

    Original = Updating;
    Console.ReadKey();
}

I'm using refs for performance but I'm not sure if it does any good.

Answer 1

Naming

In C#, it is conventional to use camelCase (first letter smallcase) for method parameters and local method variables. So original instead of Original, and count instead of Count.

I also find Updating a quite confusing name. Usually variable names are nouns, whereas this sounds like a verb or adjective. Plus in Main, by the time it's been assigned a value it's not going to change any more anyway

ref

The ref keyword is irrelevant to what you're doing. I'm not sure what performance benefit you expect them to have, but I'd guess it's based on a misunderstanding of what the keyword actually does. It makes the code a little harder to read too, because it's hard to understand why the keywords are there.

Single-line for loop

In your code you have:

for (var t = 0; t < Count; t++) IDs.Add(GetNextID(ref Updating));

There are three other reasonable ways you could write this:

for (var t = 0; t < Count; t++) { IDs.Add(GetNextID(ref Updating)); }

for (var t = 0; t < Count; t++) 
    IDs.Add(GetNextID(ref Updating));

for (var t = 0; t < Count; t++) 
{
    IDs.Add(GetNextID(ref Updating));
}

Of these four, the one you picked is my least favourite. It's not found very commonly in C# so there's some cognitive friction when reading something written in that style.

Of the other three that I posted, most people consider the second to be bad practice because it is easy to make a mistake when inserting additional lines. I don't wholly buy into this personally but you should still probably pick one of the other two.

Types

While technically your numbers fit into ushorts, I wouldn't get into a habit of using integer types other than int unless you have a reason to. Unfortunately C# has relatively poor support for using multiple numeric types together in certain situations- e.g. as a generic type parameters.

Having to put Converts all over the place takes time, makes the code harder to read, and is dangerous as you end up with potential run-time (rather than compile-time) failures.

This isn't to say don't use other integer types, just make sure there's a good reason, and think through whether there's likely to be issues in the future. I've been bitten by this a few times myself.

Side-effects

It's unexpected that GetNextID would modify Updating, especially as the method returns something. You should probably have it just return the value, then let the method which calls it take charge of inserting the value. At the very least, give it a name that makes it clear it will have a side-effect beyond just returning a value.

LINQ extension power

Jude M already mentioned Enumerable.Range. There are other very powerful LINQ extensions that reduce this entire task to a few very terse lines of code.

var exclude = original.Except(delete);
var unused = Enumerable.Range(0, Int32.MaxValue).Except(exclude).Take(8);

Enumerable.Range is lazy, so that scary Int32.MaxValue won't actually have a performance impact, this will only keep evaluating until it finds 8 values not in your list.

Answer 2

Here is a tidier solution that uses the same Except() method you used to set up your example case:

public static int InsertLowestUnused( IList<int> used ) {
    int lowestUnused = Enumerable.Range( 1, int.MaxValue )
                                 .Except( used )
                                 .First();
    used.Insert( lowestUnused-1, lowestUnused ); // -1 for 0-based
    return lowestUnused;
}

The keys to brevity here are Enumerable.Range(), which just lists the integers from its first argument to just before its last, and taking advantage of knowing which index to insert at from the value itself.

On a tangential matter, you should basically never use ref for performance-related reasons. It has a meaning. You should let the compiler handle every performance consideration other than the structure of your code until you are an expert in general, an expert in the specific platform, looking at data saying you need to do so, and testing each change for effect. In this specific case, ref is very likely slower because it adds a level of indirection and prevents the compiler and JITer from being sure of things they otherwise would take advantage of when optimizing your code.