I am trying to improve the MaxMin method such that the number of comparisons is

Question

I am trying to improve the MaxMin method such that the number of comparisons is 3n/22. the method I attach below only give me the number of comparison is 2+C(n/2)+C(n/2). please help, thank you

public class MinMax {
  
  
public static void main(String[] args) {
int[] array = new int[]{4, 7, 2, 10, 345, 28, 1, 5, 0, -10, -4098, 23, 0};

Pair expected = new Pair(-4098, 345);
Pair actual = MinMax.mmB(0, array.length-1, array);
if (actual.alpha != expected.alpha) {
System.out.println("Min value incorrect. Expected: "+expected.alpha+" but got: "+actual.alpha);
} else if (actual.omega != expected.omega) {
System.out.println("Max value incorrect. Expected: "+expected.omega+" but got: "+actual.omega);
} else {
System.out.println("Test Passed"+actual.alpha +" "+ actual.omega);
}
}

public static Pair mmA(int lB, int uB, int[] array){
if (uB == lB){
return new Pair(array[lB], array[uB]);
}
else if (uB - lB == 1) {
int smallest = Math.min(array[lB], array[uB]);
int largest = Math.max(array[lB], array[uB]);
return new Pair(smallest, largest);
}
else {
int mid = (lB + uB)/2;
Pair First = mmA(lB, mid, array);
Pair Next = mmA(mid+1, uB, array);
int smallest = Math.min(First.alpha, Next.alpha);
int largest= Math.max(First.omega, Next.omega);
return new Pair(smallest, largest);
}
}

Explanation / Answer

Code:

class Pair{
int alpha;
int omega;
public Pair(int min, int max)
{
alpha = min;
omega = max;
}

  
}
public class MinMax {
  
  
public static void main(String[] args) {
int[] array = new int[]{4, 7, 2, 10, 345, 28, 1, 5, 0, -10, -4098, 23, 0};

Pair expected = new Pair(-4098, 345);
Pair actual = MinMax.mmB(0, array.length-1, array);
if (actual.alpha != expected.alpha) {
System.out.println("Min value incorrect. Expected: "+expected.alpha+" but got: "+actual.alpha);
} else if (actual.omega != expected.omega) {
System.out.println("Max value incorrect. Expected: "+expected.omega+" but got: "+actual.omega);
} else {
System.out.println("Test Passed"+actual.alpha +" "+ actual.omega);
}
}
public static Pair mmB(int l, int r, int[] array)
{
Pair res = new Pair(0,0);
int i,min,max;
if(array[l]<array[l+1])
{
res.alpha = array[l];
res.omega = array[l+1];
}
else
{
res.omega = array[l];
res.alpha = array[l+1];
}
// find min, max of two elements, then compare min with min and max with max
// instead of comparing an element with min, max
for( i=2;i<r;i=i+2)// 3 comparisions for two elements
{
if(array[i]<array[i+1])// one
{
min=array[i];
max=array[i+1];
}
else
{
max=array[i];
min=array[i+1];
}
if(min<res.alpha) // two
res.alpha = min;
if(max>res.omega) // three
res.omega = max;
}
if(i==r)// if number of elements is odd
{
if(res.alpha > array[i])
res.alpha = array[i];
if(res.omega < array[i] )
res.omega = array[i];
}
return res;
}
}

Output:

calculation:

if(array[l]<array[l+1])
{
res.alpha = array[l];
res.omega = array[l+1];
}
else
{
res.omega = array[l];
res.alpha = array[l+1];
}

this will take one comparision

  for( i=2;i<r;i=i+2)// 3 comparisions for two elements
{
if(array[i]<array[i+1])// one
{
min=array[i];
max=array[i+1];
}
else
{
max=array[i];
min=array[i+1];
}
if(min<res.alpha) // two
res.alpha = min;
if(max>res.omega) // three
res.omega = max;
}

this will take 3*(n-2)/2 comparisions = 3n/2 -3

hence total it will take 3n/2 - 2 comparisions

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.