# 53-II.0～n-1中缺失的数字

### 一、 题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: \[0,1,3]

输出: 2

示例 2:

输入: \[0,1,2,3,4,5,6,7,9]

输出: 8

限制：

1 <= 数组长度 <= 10000

来源：力扣（LeetCode）

链接：<https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof>

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 二、 分析

#### 2.1 下标匹配

本题为有序的数据，因此可以通过下标匹配来寻找缺失的数字

```
func missingNumber(_ nums: [Int]) -> Int {
    var tmp = 0
    
    for i in nums {
        if tmp != i {
            return tmp
        }
        else {
            tmp += 1
        }
    }
    
    return tmp
}
```

#### 2.2 二分法

排序数组中的搜索问题，首先可以想到 `二分法` 解决，时间复杂度降低为了 O(logN)。

![1](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-3f2b09c5b29a0f489a297ccea1f1cb6aac11ec21%2F53-II.png?alt=media)

```
func missingNumber(_ nums: [Int]) -> Int {
    var per = 0, aft = nums.count - 1
    while per <= aft {
        // 求中间下标
        let m = (per + aft) / 2

        if nums[m] == m {
            per = m + 1
        }
        else {
            aft = m - 1
        }
    }
    return per
}
```