Difference between revisions of "TADM2E 4.34"
From Algorithm Wiki
| (3 intermediate revisions by one other user not shown) | |||
| Line 3: | Line 3: | ||
<pre> | <pre> | ||
FindMinIntMissing(A): | FindMinIntMissing(A): | ||
| − | // elements in the array are continuous, the smallest missing integer | + | // Trivial case 1 |
| − | if(A[n - 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 | // there is a gap in A, find the gap that is smallest | ||
| Line 31: | Line 31: | ||
return findGap(A, first, mid); | return findGap(A, first, mid); | ||
</pre> | </pre> | ||
| + | |||
| + | |||
| + | ---- | ||
| + | |||
| + | 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. | ||
| + | --[[User:Ajitq|Ajitq]] ([[User talk:Ajitq|talk]]) 10:01, 5 May 2018 (UTC) | ||
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)
