Find the first "missing" number in a sorted list

Based on algorithm provided by @phs

int findFirstMissing(int array[], int start , int end){

    if(end<=start+1){
        return start+1;
    }
    else{

        int mid = start + (end-start)/2;

        if((array[mid] - array[start]) != (mid-start))
            return findFirstMissing(array, start, mid);
        else
            return findFirstMissing(array, mid+1, end);

    }
}

Use binary search. If a range of numbers has no hole, then the difference between the end and start of the range will also be the number of entries in the range.

You can therefore begin with the entire list of numbers, and chop off either the first or second half based on whether the first half has a gap. Eventually you will come to a range with two entries with a hole in the middle.

The time complexity of this is O(log N). Contrast to a linear scan, whose worst case is O(N).

Since numbers from 0 to n - 1 are sorted in an array, the first numbers should be same as their indexes. That's to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. If the missing number is denoted as m. Numbers less then m are located at cells with indexes same as values.

The number m + 1 is located at a cell with index m, The number m + 2 is located at a cell with index m + 1, and so on. We can see that, the missing number m is the first cell whose value is not identical to its value.

Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(lg n) time based on the binary search algorithm as implemented below:

int getOnceNumber_sorted(int[] numbers)
{
    int length = numbers.length
    int left = 0;
    int right = length - 1;
    while(left <= right)
    {
        int middle = (right + left) >> 1;
        if(numbers[middle] != middle)
        {
            if(middle == 0 || numbers[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }


    return -1;
}

This solution is borrowed from my blog: http://codercareer.blogspot.com/2013/02/no-37-missing-number-in-array.html.

Based on the approach suggested by @phs above, here is the C code to do that:

#include <stdio.h>

int find_missing_number(int arr[], int len) {
    int first, middle, last;
    first = 0;
    last = len - 1;
    middle = (first + last)/2;

    while (first < last) {
        if ((arr[middle] - arr[first]) != (middle - first)) {
            /* there is a hole in the first half */
            if ((middle - first) == 1 && (arr[middle] - arr[first] > 1)) {
                return (arr[middle] - 1);
            }

            last = middle;
        } else if ((arr[last] - arr[middle]) != (last - middle)) {
            /* there is a hole in the second half */
            if ((last - middle) == 1 && (arr[last] - arr[middle] > 1)) {
                return (arr[middle] + 1);
            }

            first = middle;
        } else {
            /* there is no hole */
            return -1;
        }

        middle = (first + last)/2;
    }

    /* there is no hole */
    return -1;
}

int main() {
    int arr[] = {3, 5, 1};
    printf("%d", find_missing_number(arr, sizeof arr/(sizeof arr[0]))); /* prints 4 */
    return 0;
}