Difference between revisions of "TADM2E 4.34"

Latest revision as of 10:01, 5 May 2018

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 be n + 1
    else if(A[n - 1] == n)
    {
        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);           

If there were no gaps, Ai would be i. If we tested the mid-point (mid=n/2) and we found that Amid = mid, we would know that the gap is somewhere on the right side of the midpoint. If not, we know the gap is on the left side. We then recurse to find the gap. --Ajitq (talk) 10:01, 5 May 2018 (UTC)