這是在TL討論中Liu xinyu給出的一個例子，覺得思路挺有啟發的，所以整理記錄一下。

　　給定一個數組，其內容是一些隨機的、不重復的正整數，如：

　　{4, 23, 1, 8, 9, 21, 6, 12}

　　要求找出不在數組中出現的最小的那個數，比如這個數組中未在數組中出現的最小值是：2

　　這個問題實際應用的原型可以是一個ID分配系統，其使用一個數組來保存已分配的ID，每次回收就從數組中刪除一個元素(O(n))，而分配則需要找到最小的那個可用的ID，就是這個算法要做的事情。

　　這個問題從naive的解法到快速的解法的思路轉換是十分巧妙的，當然，如果之前沒有接觸過類似的題，注意到這個特性應該不是一件很容易的事。

　　設數組為A，大小為n，下標從1開始，下面是一系列逐步改進的算法：

一、窮舉查找

　　一般的問題都可以通過這種很暴力的方式來做，從1到n逐個判斷是否在數組中：

　　MIN-AVAILABLE-NUM(A, n)

　　　　for i = 1 to n

　　　　　　do if i not in A 

　　　　　　　    then return i

　　      return n+1

　　顯然，這里的算法復雜度是O(n^2)

二、先排序再二分查找

　　第一種方法，每次查找都是線性查找，要改進最先想到的自然是二分查找，二分查找的前提是有序， 所以：

1. 先排序，用O(nlgn)的快速排序、歸并排序或者堆排序；因為數組中的元素是一些自然數，我們甚至可以使用O(n) 的基數排序，當然，需要更多的內存。
2. 對1..n進行判斷，復雜度也為O(nlgn)

　　所以，整體的算法復雜度為O(nlgn)

三、該數組的一個特性

　　其實仔細觀察該數組A[1]..A[n]，我們可以得出一個結論：如果該數組中存在未被使用的數，那么Max(A) > n。

　　證明很簡單，假設Max(A) <= n，由于該數組大小為n，那么該數組中的元素只能是從1到n的某個排列，從而得出該數組中不存在未被使用的數，矛盾。

　　這個特性和抽屜原理有些類似之處。

　　從而我們可以有另外一個方法：

1. 先排序
2. 再利用該特性搜索

　　MIN-AVAILABLE-NUM(A, n)

　　　　for i = 1 to n

　　　　　　do A[i] > i

　　　　　　　    then return i

　　      return n+1

　　注意到，如果我們使用基數排序，可以將復雜度降低到O(n)。

四、一個線性時間，線性空間的算法

　　第三個算法雖然能達到理論意義上的O(n)，但是基數排序隱含的常數因子較大，而且不是原地排序，這里給出一個不需要排序的算法：

　　MIN-AVAILABLE-NUM(A, n)

　　　　for i = 1 to n

　　　　　　B[i] = 0

　　　　for i = 1 to n

　　　　　　do if A[i] < n

　　　　　　　    then B[A[i]] = 1

　　      for  i = 1 to n

　　　　　　if(B[i] == 0) return i;

　　　　 return n+1;

　　這里使用一個輔助數組B來表示1到n這些數是否存在在數組A中，只要不存在就將其標為0，最后在B中找到第一個值為0的便是我們要找的那個元素；如果B中元素全為1，這說明A使用了所有1到n這些數，那么返回的便是下一個n+1.

　　此處無須排序，且復雜度為O(n)，但需要一個額外的O(n)的數組。

五、一個線性時間、常數空間的算法

　　利用快速排序的原理，我們可以在不使用額外數組的情況下達到O(n)的效率，原理為：

　　取1到n的中間值m = (1 + n)/2，用m將數組分成A1, A2兩個部分，A1中的元素全部小于等于m，A2中的元素全部大于m（注意此處用的是下標，而不是A[m]），如果A1的大小為m，則空閑元素在A2中，這在前面證明過，然后就在A2中應用同樣的方法。

　　MIN-AVAILABLE-NUM(A, low, up)

　　　　if(low == up) return low

　　　　m = (low + up) / 2

　　　　split = partition(A, low, up, m)

　　　　if a[split] == m 

　　　　   then return MIN-AVAILABLE-NUM(A, low, split)

　　      else return MIN-AVAILABLE-NUM(A, split+1, up)

　　這里遞歸式為：T(n) = T(n/2) + O(n)，根據主定理的第三種情況，復雜度為O(n)，其實也就是一個等比數列：n + n/2 + n/4...

　　但是，此處因為用到遞歸，所以空間復雜度其實是O(Lgn)，所以可以用循環來代替：

　　MIN-AVAILABLE-NUM(A, low, up)
while low != up
m = (low + up) / 2
split = partition(low, up, m)
if A[split] == m 
then low = split + 1
else up = split - 1
return low