TADM2E 4.34 - Revision history

Ajitq at 10:01, 5 May 2018

2018-05-05T10:01:30Z

Rainhaven at 00:27, 23 September 2016

2016-09-23T00:27:10Z

Rainhaven at 00:25, 23 September 2016

2016-09-23T00:25:03Z

Rainhaven at 00:24, 23 September 2016

2016-09-23T00:24:41Z

Rainhaven at 00:20, 23 September 2016

2016-09-23T00:20:04Z

Rainhaven: Created page with "Assume array indices are zero based, use modified binary search to find the smallest integer missing:

 FindMinIntMissing(A):     // elements in the array are continuous,..."

2016-09-23T00:13:41Z

Created page with "Assume array indices are zero based, use modified binary search to find the smallest integer missing: <pre> FindMinIntMissing(A): // elements in the array are continuous,..."

New page

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

<pre>
FindMinIntMissing(A):
// elements in the array are continuous, the smallest missing integer is either 1 if A[0] is not 1, or n + 1 otherwise
if(A[n - 1] - A[0] == n - 1)
{
if(A[0] > 1)
return 1;
else
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);
</pre>

← Older revision		Revision as of 10:01, 5 May 2018
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)

@@ Line 7: / Line 7: @@
          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] - A[0] == n - 1)
+     else if(A[n - 1] == n)
+     {
          return n + 1;

@@ Line 6: / Line 6: @@
      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
+     // 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] - A[0] == n - 1)
+     {

@@ Line 14: / Line 14: @@
      else
+     {
-         return findGap(a, 0, n - 1);
+         return findGap(A, 0, n - 1);
+     }
@@ Line 26: / Line 26: @@
         // 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);
+            return findGap(A, mid, last);
         // looking for the gap in the first half
         else
-            return findGap(a, first, mid);
+            return findGap(A, first, mid);
 </pre>