# TADM2E 4.34

From Algorithm Wiki

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)