# 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](/files/uEdwaQpOg2NqFuTM9Ccb)

```
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
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/53ii.0n1-zhong-que-shi-de-shu-zi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.