Missing Number

Question: Given an array of integers of size n. This array has integer values starting from x, incrementing by 1. The final array element is n+x (instead of n + x - 1) i.e. it is missing one integer in between. Write a function to identify this missing number.


Example: array[5] = { 2,3,4,6,7 }; missing number is 5.


Time Complexity: O(log n)



int missing_number(int *a, int len)
{
    int mid = len / 2;


    if (len == 1) {
        printf ("missing number is %d\n", a[0] + 1);
        return (a[0] + 1);
    }


    if ((a[0] + mid) == a[mid])
    {
        // first half of array is not missing a number
        missing_number(&a[mid], len - mid);
    } else {
        // second half of array is not missing a number
        missing_number(a, mid);
    }
}