查找不在列表中的最小非负整数的算法

给定一个整数列表，我怎样才能最好地找到一个整数not在列表中？

该列表可能非常大，并且整数也可能很大（即 BigIntegers，而不仅仅是 32 位整数）。

如果有什么区别，列表“可能”已排序，即 99% 的时间都会排序，但我不能依赖总是排序。

Edit -

澄清一下，给定列表 {0, 1, 3, 4, 7}，可接受的解决方案的示例是 -2, 2, 8 和 10012，但我更愿意找到最小的非负解决方案（即 2）是否有一种算法可以找到它而不需要对整个列表进行排序。

一种简单的方法是迭代列表以获得最高值n，那么你就知道n+1不在列表中。

Edit:

找到最小的未使用的正数的方法是从零开始并扫描列表以查找该数字，如果找到该数字则重新开始并增加。为了提高效率，并利用列表被排序的高概率，您可以将小于当前数字的数字移动到列表中未使用的部分。

该方法使用列表的开头作为较低数字的存储空间，startIndex变量跟踪相关数字的开始位置：

public static int GetSmallest(int[] items) {
    int startIndex = 0;
    int result = 0;
    int i = 0;
    while (i < items.Length) {
        if (items[i] == result) {
            result++;
            i = startIndex;
        } else {
            if (items[i] < result) {
                if (i != startIndex) {
                    int temp = items[startIndex];
                    items[startIndex] = items[i];
                    items[i] = temp;
                }
                startIndex++;
            }
            i++;
        }
    }
    return result;
}

我做了一个性能测试，创建了包含从 0 到 19999 的 100000 个随机数的列表，这使得平均最低数字约为 150。在测试运行中（每个测试列表有 1000 个），该方法平均发现未排序列表中的最小数字为8.2 毫秒，在排序列表中平均为 0.32 毫秒。

（我还没有检查该方法在什么状态下离开列表，因为它可能会交换其中的一些项目。它至少会留下包含相同项目的列表，并且当它在列表中向下移动较小的值时，我认为它应该实际上每次搜索都会变得更加排序。）