Check if number is the median in a double array

Question

You have to use a for-each loop to check if the number you enter as a parameter is the median in an array you also enter as a parameter. I thought my logic was fine but it returns false for everything. Any guidance would be appreciated.

public static boolean isMedian(double[] arr, double m)
    {
        int countLow = 0;
        int countHigh = 0;
        int count = 0;
        for(double e : arr)
            if(arr[count] > m)
            {
                countHigh++;
                count++;
            }
            else if(arr[count] < m)
            {
                countLow++;
                count++;
            }
        if(countLow == countHigh)
            return true;
        else
            return false;


    }

    public static void main(String[] args)
    {

        double[] array = {1.0, 2.0, 3.0, 4.0 , 5.0, 6.0, 7.0};
        System.out.println(isMedian(array, 4.0));
    }

Answer 1

The basic answer to the question, which was stated by Anonymous, is that with the extended for loop, you don't want to reference the array by index. The assignment was to use an extended for loop, and I wanted to go with the (one-pass, no sorting, so O(n) unless I'm missing something) basic algorithm specified in the question. The idea that you're the median if the same number of numbers are above you as below you, can break down in a couple of ways.

1) As Andreas pointed out, if your number occurs more than once for example 1, 3, 3 and you ask if 3 is the median, it will say no, because the number of numbers below differs from the number of numbers above.

2) When there are an even number of numbers, even though you have the same number of numbers below and above, you might still not be smack in the middle. For 1 and 3, only 2 will do, not 2.5.

So I adapted the algorithm to handle all those special cases. That required tracking how many times the number itself occurred (or at least that was simplest, one could also calculate that by subtracting the sum of the other counts from the number of numbers) as well as the numbers immediately below and above in case we have to average them.

It's a bit spaghetti-like, and possibly would be better if there were separate methods for odd and even sizes, or if one thought really hard about unifying parts of various cases. But after testing all the cases mentioned, I think it works. In the comments I noted possible tweaks, such as watching out more carefully for floating point errors in calculation (one might also do so in comparisons).

public static boolean isMedian(double[] arr, double m) {
        int countLow = 0;
        int countHigh = 0;
        int countM = 0; //track how many times the candidate number itself occurs
        double supLow = 0.0; //maximum number below m, only meaningful if countLow is positive
        double infHigh = 0.0; //minimum number above m, only meaningful if countHigh is positive
        // int count = 0; as Anonymous said, not needed extended for loop handles looping over all e in arr
        for (double e: arr)
            if (e > m) {
                if (countHigh == 0 || e < infHigh) {
                    infHigh = e;
                }
                countHigh++;
            }
        else if (e < m) {
            if (countLow == 0 || e > supLow) {
                supLow = e;
            }
            countLow++;
        } else //e==m
        {
            countM++;
        }
        //System.out.println("countLow = "+countLow+" countHigh = "+ countHigh + " countM = " + countM);
        if (arr.length % 2 == 1) { //odd sized array, easier case because no averaging needed
            if (countM == 0) { //number does not occur at all, so certainly not in the middle
                return false;
            } else if (countM == 1) //number occurs once, is it in the middle?
            {
                return (countLow == countHigh);
            } else { //number occurs more than once, is one of the occurrences in the middle?
                int mStartIndex = countLow; //were the array to be sorted, the 0-based index of the first occurrence of m
                int mEndIndex = mStartIndex + countM - 1; //were the array to be sorted, the 0-based index of the last occurrence of m
                int middleIndex = arr.length / 2; // were the array to be sorted, 0-based index of the middle spot
                return (middleIndex >= mStartIndex && middleIndex <= mEndIndex);
            }
        }
        //still here, must be even size
        //System.out.println("supLow = "+supLow+" infHigh = "+ infHigh);
        if (countM == 0) {
            if (countLow != countHigh) {
                return false;
            } else { //our number is between the two middle numbers, but is it the average?
                return ((m + m) == (supLow + infHigh)); //using == with floating point addition, if that proves unreliable, do Math.abs(2*m-supLow-infHigh)<EPSILON
            }
        } else if (countM == 1) //number occurs once, which cannot be the median, if it is not in the 2 middle spots, it is lower or higher than both, even if it is, it cannot be the average of itself and a different number
        {
            return false;
        } else { //number occurs more than once, does it occupy both middle spots?
            int mStartIndex = countLow; //were the array to be sorted, the 0-based index of the first occurrence of m
            int mEndIndex = mStartIndex + countM - 1; //were the array to be sorted, the 0-based index of the last occurrence of m
            int firstMiddleIndex = arr.length / 2 - 1; // were the array to be sorted, 0-based index of the first of two middle spots
            int secondMiddleIndex = firstMiddleIndex + 1;
            return (firstMiddleIndex >= mStartIndex && secondMiddleIndex <= mEndIndex);
        }
    }

REVISION: broke up the code so no method is too long. Also bracketed for loop bodies.

private static boolean isMedianForOdd(double[] arr, double m) {
int countLow = 0;
int countHigh = 0;
for (double e: arr) {
    if (e > m) {
        countHigh++;
    } else if (e < m) {
        countLow++;
    }
}

int countM = arr.length - countHigh - countLow; //how many times the candidate number itself occurs

if (countM == 0) { //number does not occur at all, so certainly not in the middle
    return false;
} else if (countM == 1) //number occurs once, is it in the middle?
{
    return (countLow == countHigh);
} else { //number occurs more than once, is one of the occurrences in the middle?
    int mStartIndex = countLow; //were the array to be sorted, the 0-based index of the first occurrence of m
    int mEndIndex = mStartIndex + countM - 1; //were the array to be sorted, the 0-based index of the last occurrence of m
    int middleIndex = arr.length / 2; // were the array to be sorted, 0-based index of the middle spot
    return (middleIndex >= mStartIndex && middleIndex <= mEndIndex);
}


}

private static boolean isMedianForEven(double[] arr, double m) {
    int countLow = 0;
    int countHigh = 0;
    double supLow = 0.0; //maximum number below m, only meaningful if countLow is positive
    double infHigh = 0.0; //minimum number above m, only meaningful if countHigh is positive
    for (double e: arr) {
        if (e > m) {
            if (countHigh == 0 || e < infHigh) {
                infHigh = e;
            }
            countHigh++;
        } else if (e < m) {
            if (countLow == 0 || e > supLow) {
                supLow = e;
            }
            countLow++;
        }
    }
    int countM = arr.length - countHigh - countLow; //how many times the candidate number itself occurs
    if (countM == 0) {
        if (countLow != countHigh) {
            return false;
        } else { //our number is between the two middle numbers, but is it the average?
            return ((m + m) == (supLow + infHigh)); //using == with floating point addition, if that proves unreliable, do Math.abs(2*m-supLow-infHigh)<EPSILON
        }
    } else if (countM == 1) //number occurs once, which cannot be the median, if it is not in the 2 middle spots, it is lower or higher than both, even if it is, it cannot be the average of itself and a different number
    {
        return false;
    } else { //number occurs more than once, does it occupy both middle spots?
        int mStartIndex = countLow; //were the array to be sorted, the 0-based index of the first occurrence of m
        int mEndIndex = mStartIndex + countM - 1; //were the array to be sorted, the 0-based index of the last occurrence of m
        int firstMiddleIndex = arr.length / 2 - 1; // were the array to be sorted, 0-based index of the first of two middle spots
        int secondMiddleIndex = firstMiddleIndex + 1;
        return (firstMiddleIndex >= mStartIndex && secondMiddleIndex <= mEndIndex);
    }
}

public static boolean isMedian(double[] arr, double m) {
    if (arr.length % 2 == 1) {
        return isMedianForOdd(arr, m);
    } else {
        return isMedianForEven(arr, m);
    }
}

REVISION 2: return(Math.abs(2*m-supLow-infHigh)< 0.000001);//avoid floating point issues, feel free to adjust the right hand side

should replace the line:

return ((m + m) == (supLow + infHigh));

or (MINOR REVISION 2'), with credit to Dawood says reinstate Monica for the idea, replace it with this set of lines if you do not wish to mess with specifying the precision.

BigDecimal bdM =  BigDecimal.valueOf(m);
bdM = bdM.add(bdM).stripTrailingZeros();//2*m
BigDecimal bdInfSup =  BigDecimal.valueOf(supLow);
bdInfSup = bdInfSup.add(BigDecimal.valueOf(infHigh)).stripTrailingZeros();
return(bdM.equals(bdInfSup));

Answer 2

Here is a method that will accomplish the task for you:

    public static boolean isMedian(double[] arr, double m){
        double med;
        ArrayList<Double> a = new ArrayList<Double>();
        a.add(arr[0]);
        a.add(Double.MAX_VALUE);
        for(double 1: arr){
            for(int j=0; j<a.size()&&j>=-10;j++){
                if(i<a.get(j)){
                    a.add(j,i);
                    j=-200;
                }
            }
        }
        a.remove(a.size()-1);
        if(arr.length%2==1){
            med=a.get(arr.length/2);
        } else{
            med=(double)(a.get(arr.length/2)+a.get(arr.length/2-1))/2.0;
        }
        if (med==m)return true;
        return false;
    }

Answer 3

You don’t change count when you’re at the median. This is why you should use e instead:

public static boolean isMedian(double[] arr, double m)
{
    int countLow = 0;
    int countHigh = 0;
    for(double e : arr)
        if(e > m)
        {
            countHigh++;
        }
        else if(e < m)
        {
            countLow++;
        }
    if(countLow == countHigh)
        return true;
    else
        return false;


}

public static void main(String[] args)
{

    double[] array = {1.0, 2.0, 3.0, 4.0 , 5.0, 6.0, 7.0};
    System.out.println(isMedian(array, 4.0));
}