Вот решение за O(n^2), можно сделать за O(n*logn) с помощью сортировки или за O(n) если массив уже отсортирован
public static int NextId(int[] ids)
{
for (int i = 0; i < ids.Length; i++)
{
if (Array.IndexOf(ids, i) == -1)
{
return i;
}
}
return ids.Length;
}
