# 尋找最小的遺失號碼 > 原文： [https://www.geeksforgeeks.org/find-the-first-missing-number/](https://www.geeksforgeeks.org/find-the-first-missing-number/) 給定**排序的**數組，其中包含`n`個不同的整數，其中每個整數的范圍為 0 到`m-1`，`m > n`。 查找數組中缺少的最小數字。 示例 ``` 輸入: {0,1,2,6,9}, n = 5, m = 10 輸出: 3 輸入: {4, 5, 10, 11}, n = 4, m = 12 輸出: 0 輸入: {0, 1, 2, 3}, n = 4, m = 5 輸出: 4 輸入: {0, 1, 2, 3, 4, 5, 6, 7, 10}, n = 9, m = 11 輸出: 8 ``` 感謝 Ravichandra 建議采用以下兩種方法。 **方法 1（使用二分搜索）** 對于`i = 0`到`m-1`，對數組中的`i`進行二分搜索。 如果數組中不存在`i`，則返回`i`。 時間復雜度：`O(m log n)` **方法 2（線性搜索）** 如果`arr[0]`不為 0，則返回 0。否則，從索引 0 開始遍歷輸入數組，并針對元素對`a[i]`和`a[i + 1]`，找出它們之間的區別。 如果差大于 1，則`a[i] +1`是丟失的數字。 時間復雜度：`O(n)` **方法 3（使用修改的二分搜索）** 感謝 yasein 和 **Jams** 提出了此方法。 在標準二分搜索過程中，將要搜索的元素與中間元素進行比較，然后根據比較結果，確定搜索是結束還是移至左半部分或右半部分。 在此方法中，我們修改了標準的二分搜索算法，以比較中間元素及其索引，并在此比較的基礎上做出決策。 …1）如果第一個元素與其索引不同，則返回第一個索引 …2）否則獲得中間索引，例如`mid` …………a）如果`arr[mid]`大于`mid`則要求 元素位于左半部分。 …………b）另外，所需元素位于右半部分。 ## C++ ```cpp // C++ program to find the smallest elements // missing in a sorted array. #include<bits/stdc++.h> using namespace std; int findFirstMissing(int array[],? ????????????????????int start, int end) { ????if (start > end) ????????return end + 1; ????if (start != array[start]) ????????return start; ????int mid = (start + end) / 2; ????// Left half has all elements? ????// from 0 to mid ????if (array[mid] == mid) ????????return findFirstMissing(array,? ????????????????????????????mid+1, end); ????return findFirstMissing(array, start, mid); } // Driver code int main() { ????int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10}; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "Smallest missing element is " << ????????findFirstMissing(arr, 0, n-1) << endl; } // This code is contributed by // Shivi_Aggarwal? ```