题目描述

一个长度为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

解题思路

由于数组是排序递增的数组，因此可以使用二分法进行查找，缺失的数字有个特点，即其值与其在数组中的索引值不相等，因此通过二分法求出数组中间的数字，若其值与数组中的索引值相等，则缺失的值在中间数字的右半部分，若缺失的值与其在数组中的索引值不相等，则缺失的值在中间数字的左半部分，以此类推。

代码

int missingNumber(int* nums, int numsSize){
    int i = 0, j = numsSize - 1;

    while(i <= j)
    {
        int middle = (i + j) / 2;
        if(nums[middle] == middle)
            i = middle + 1;
        else
            j = middle - 1;
    }

    return i;
}

测试代码及结果

#include<stdio.h>

int missingNumber(int *nums, int numsSize);

int main(void)
{
    // 功能测试
    int nums1[] = { 1, 2, 3, 4, 5, 6, 7 }; // 缺失值位于数组开始位置
    int res1 = missingNumber(nums1, sizeof(nums1) / sizeof(int));
    printf("res1 = %d\n", res1);

    int nums2[] = { 0, 1, 2, 4, 5, 6, 7 }; // 缺失值位于数组中间位置
    int res2 = missingNumber(nums2, sizeof(nums2) / sizeof(int));
    printf("res2 = %d\n", res2);

    int nums3[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; // 缺失值位于数组末尾位置
    int res3 = missingNumber(nums3, sizeof(nums3) / sizeof(int));
    printf("res3 = %d\n", res3);

    // 边界值测试
    int nums4[] = {1};
    int res4 = missingNumber(nums4, sizeof(nums4) / sizeof(int));
    printf("res4 = %d\n", res4);

    // 特殊输入测试
    int *nums5 = NULL;
    int res5 = missingNumber(nums5, 0);
    printf("res5 = %d\n", res5);

    return 0;
}

执行结果

时间复杂度：O(nlogn), 空间复杂度：O(1)