Difference between revisions of "TADM2E 4.34"

Revision as of 00:24, 23 September 2016

Assume array indices are zero based, use modified binary search to find the smallest integer missing:

FindMinIntMissing(A):
    // Trivial case 1
    if(A[0] > 1)
        return 1;
    // Trivial case 2: elements in the array are continuous from 1 to n, the smallest missing integer must n + 1
    else if(A[n - 1] - A[0] == n - 1)
    {
        return n + 1;
    }
    // there is a gap in A, find the gap that is smallest
    else
    {
        return findGap(A, 0, n - 1);
    }

FindGap(A, first, last):
    // only two elements left, the smallest gap must be the integer right after A[first]
    if(last == first + 1)
        return A[first] + 1;
    // recursively looking for the partition containing the smallest gap
    else
       mid = (first + last) / 2;
       // first half doesn't have gap, looking for gap in the second half
       if(A[mid] - A[first] == mid - first)
           return findGap(A, mid, last);
       // looking for the gap in the first half
       else
           return findGap(A, first, mid);