Median of two sorted equal sized arrays on combination

Question

The comprehensive description of the problem can be found here. I'm looking for code review, clever optimizations, adherence to best practices. etc.

This code is also a correction of code previously posted here.

/**
 * @author javadeveloper
 */
public final class MedianOfTwoSortedArrays {

    private MedianOfTwoSortedArrays() {}

    private static boolean isMedian (int[] a1, int[] a2, int pos) {
        if (pos == 0 || pos == (a1.length - 1)) return true;
        return (a1[pos] >= a2[pos]) && (a1[pos] <= a2[pos + 1]);
    }


    private static double calculateMedian(int[] a1, int a1median, int[] a2, int a2median) {
        if (a1median == 0 || a2median == 0 || a1[a2median] < a1[a1median + 1]) return (a1[a1median] + a2[a2median])/2.0;
        return ((a1[a1median] + a1[a1median + 1])/2.0);
    }

    /**
     * Given two sorted arrays of same length it returns the median.
     * If arrays are not of equal length throws the IllegalArgumentException.
     * If arrays are not sorted the results can be unpredictable.
     * 
     * @param a1    the first sorted array
     * @param a2    the second sorted array 
     * @return      the median of the two integers or null if no such median is found due to illegal input.
     */
    public static Double median (int[] a1, int[] a2) {
        if (a1.length != a2.length) throw new IllegalArgumentException("The argument thrown is illegal");

        int lb = 0;
        int hb = a1.length - 1;

        while (lb <= hb) {
            int a1Median = (lb + hb)/2;
            int a2Median = (a2.length - 1) - a1Median;

            // is one of the element constituting the median in first array ?
            if (isMedian(a1, a2, a1Median)) {
                return calculateMedian(a1, a1Median, a2, a2Median);
            }

            // is one of the element constituting the median in second array ?
            if (isMedian(a2, a1, a2Median)) {
                return calculateMedian(a2, a2Median, a1, a1Median);
            }

            if (a1[a1Median] < a2[a2Median]) {
                lb = a1Median + 1;
            }

            if (a1[a1Median] > a2[a2Median]) {
                hb = a1Median - 1;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] a1 = {1, 3, 5, 7, 9};
        int[] a2 = {2, 4, 6, 8, 10};
        System.out.println("Expected 5.5, Actual " + median (a1, a2));


        int[] a3 = {1, 3, 5, 7, 9, 100};
        int[] a4 = {2, 4, 6, 8, 10, 200};
        System.out.println("Expected 6.5, Actual " + median (a3, a4));

        int[] a5 = {1, 2, 3, 4};
        int[] a6 = {5, 6, 7, 8};
        System.out.println("Expected 4.5, Actual " + median (a5, a6));

        int[] a7 = {5, 6, 7, 8};
        int[] a8 = {1, 2, 3, 4};
        System.out.println("Expected 4.5, Actual " + median (a7, a8));  

        int[] a9 =  {1, 1, 10, 10};
        int[] a10 = {5, 5,  5,  5};
        System.out.println("Expected 5.0, Actual " + median (a9, a10)); 

        int[] a11 = {5, 5, 5, 5};
        int[] a12 = {1, 1, 10, 10};
        System.out.println("Expected 5.0, Actual " + median (a11, a12));    
    }
}

Answer 1

Ok. Lets try to solve it with logarithmic complexity. I'm not sure that having equal sizes can help much except that we always expect even length. But I agree that we can achieve O(log(n)). I'll try to follow idea of your code (hope I were able to guess it).

We know that median would divide two arrays into four parts with indexes that:

• a[i-1] <= b[j] && a[i] >= b[j-1]
  Yep, values in lower parts (for both arrays) should be less than values in upper parts.
  Our i says that indexes [0;i) is lower part of a and [i;n) is upper. Thus we compare last value from lower with first value from upper.
• i + j == (a.length - i) + (b.length - j) => j = a.length - i
  That's looks sane. If we split first array into n of lower values and m upper values we should split second array into m lower values and n upper values to get equal amount of values in upper and lower parts.
• if we'll consider situation without restriction on equal sizes we'll need to be prepeared for situation when in one of array we'll have index of element and other will have division in two parts.
• its easier to think that:
  i = 0 means { | 1, 2, 3, 4} { 5, 6, 7, 8 | } (j = 4)
  i = 2 means {1, 3 | 5, 7} {0, 2 | 4, 8} (j = 2).

For simplicity I'll consider only n % 2 == 0 variant:

private static final class MedianLookup {
    private final int[] a, b;

    MedianLookup(int[] a, int[] b)
    {
        assert (a.length % 2) == 0; // TODO: other case
        assert a.length == b.length;
        this.a = a; this.b = b;
    }
}

Lets define our check function:

    private int cmpMedian(int i)
    {
        // i + j == (a.length - i) + (b.length - j)
        // 2*j == a.length + b.length - 2*i
        int j = a.length - i;

        // a[i-1] <= b[j] && a[i] > b[j-1]
        double lb1 = i == 0
           ? Double.NEGATIVE_INFINITY
           : a[i-1];
        double ub1 = i == a.length
           ? Double.POSITIVE_INFINITY
           : a[i];
        double lb2 = j == 0
           ? Double.NEGATIVE_INFINITY
           : b[j-1];
        double ub2 = j == b.length
           ? Double.POSITIVE_INFINITY
           : b[j];
        if (lb2 > ub1) return +1; // need to incr index
        else if (lb1 > ub2) return -1; // nedd to decr index
        else return 0;
    }

And lookup will look like:

    public double lookup()
    {
        int lb = 0, ub = a.length;
        while (lb <= ub)
        {
            int i = (lb + ub)/2;
            int answ = cmpMedian(i);
            if (answ < 0)  ub = i-1;
            else if (answ > 0) lb = i+1;
            else return calculateMedian(i);
        }
        return Double.NaN;
    }

Calculate median may look a bit more complex:

    private double calculateMedian(int i)
    {
        int j = a.length - i;

        // simple cases when arrays can be attached one to other
        if (i == 0) // b <-> a
        { return (b[j - 1] + a[0])/2.0; }
        else if (j == 0) //  a <-> b
        { return (a[i - 1] + b[0])/2.0; }

        // overlapping (search best pair)
        double lb1 = a[i-1], ub1 = a[i];
        double lb2 = b[j-1], ub2 = b[j];
        double bestSum = lb1 + ub1,
               bestDiff = ub1 - lb1;
        if ((ub2 - lb1) < bestDiff)
        { bestSum = ub2+lb1; bestDiff = ub2-lb1; }
        if ((ub1 - lb2) < bestDiff)
        { bestSum = ub1+lb2; bestDiff = ub1-lb2; }
        if ((ub2 - lb2) < bestDiff)
        { bestSum = ub2+lb2; bestDiff = ub2-lb2; }

        return bestSum/2;
    }

Updated: too many hours with Haskell language. Found integer devision in calculateMedian() for simple cases.

Now I get:

Expected 5.5, Actual 5.5
Expected 6.5, Actual 6.5
Expected 4.5, Actual 4.5
Expected 4.5, Actual 4.5
Expected 5.0, Actual 5.0
Expected 5.0, Actual 5.0
Expected 5.0, Actual 5.0

Answer 2

Short Review

I have spent some hours trying to understand what you do, and why. Given the mess I made of the previous posting of this question, I thought I should spend extra effort to get this one right.

I have failed. I cannot understand the full intent of your code, and, even though it appears to work, I have this nagging feeling that some well-constructed uses cases will cause the code to fail - you have too many edge-case conditions in the code which are not documented, and not contextualized enough to ascertain whether they work, or what conditions they are supposed to handle.

Bottom line is that your program is not understandable in a reasonable amount of time, and it was your responsibility to make your code understandable, not the reviewer's responsibility to decode your system. Just because you may have your solution 'straight' in your head, it does not mean that you have expressed it well in the code. You have to write and document the code so that someone who has only just seen the problem can understand it and the solution with 'reasonable' effort. In this case, I don't believe you have succeeded.

Longer Review

In a 'real' review there is no "reference implementation" to compare against. All there is, is a specification. In this case, the specification is to identify the median (middle value, or average of middle-pair if the data-set is even-sized). In addition to the expected result, the data is assumed to be in two equal-sized arrays of sorted data.

Given those specifications you can also make a couple of assumptions:

• the ending-dataset will always have an even number of elements (2 * x is always even for any integral value x), which means we will always be doing some form of average.
• There will always be n-1 values smaller than the smaller of the mid-point-pair, and n-1 values larger than the higher of the mid-point-pair.

OK, based on those specifications and assumptions, we can review the code, and see how it solves the problem.

1. First thing I note is that there are two variables which have names that don't seem to relate to any feature of the problem space, lb and hb. There is no comment to indicate what these variables are, so the only choice is to inspect the code to see how it is used. This means we have to trust that the code is doing the right thing just so we can understand what the intended use of the variable is.

   This is a bad practice, and is solved by using self-documenting variable names. This has been pointed out to you before. You need to start improving your code-style.

2. When I try to track down what lb and hb are supposed to be, I find that they are used as a loop condition, which does not help us in this case because the loop condition is not documented. They are also used to calculate the variables a1Median and a2Median. Unfortunately, a1Median, although it is a descriptive name, does not mean what it says it means.... it is not the Median of array a1. It starts off being the approximate midpoint of a1 (the median is the value at the midpoint, not the position of the midpoint), but then, to make things worse, the a1Median is modified in each loop! So, this descriptive variable name has the completely wrong description. This is worse than having a non-descriptive name because, now the person reading the code has to keep remembering that "a1Median is not the median of array a1"!

At this point, in any 'serious' review, you would be facing a lot of criticism. There are times when it is OK for code to be hard to read... but that is only when the problem is very complicated. What you have here is unnecessarily hard to read.

OK, after some study (and I literally mean some serious head-scratching, debugging, and paper-worked examples), I think I can see your algorithm.....

• set up lb and hb (still not sure what those are supposed to stand for - low-something and high-something ?) as pointers in to the first array.
• we will manipulate these high and low pointers to select a 'candidate' value in the first array.
• we then use the candidate point in the first array and calculate a candidate point in the second array. The second array's candidate is always going to be where there are n-1 values smaller/larger than the two candidate positions. If our candidate in array1 is x then the candidate in array2 will be array2 - x - 1 which would satisfy the midpoint-pair condition.
• if the values at these candidate positions are in fact the midpoints, then we can return a success.
• if we have a success, we do not actually know if the candidate values are in fact the actual pair, all we know is that one of the candidates is the midpoint. The other candidate may not be part of the solution if we have two of the same values on our side... in which case both of the candidates need to come from one array.
• if we do not have a success, we essentually do a 'bifurcation' of the data to do a binary search-style partitioning of the data to look for a candidate.

So, your algorithm has this isMedian() method. Unfortunately, this method re-uses two already bad variable names as parameters. We now have a different a1 and a2, which are not the same as the a1 and a2 in the calling method, because sometimes the calling method swaps the order of these.... Still, this method returns true under conditions which make no apparent sense. Why is there a median when pos == 0 ? That seems pretty arbitrary.

This same problem exists in the untangling method calculateMedian(). a1 and a2 which are not the same as before.

Speaking of untangling, why do you need to untangle? You should not get in to a tangle to start with!

Right, so you have an apparent algorithm, but there are still blanks in what it should be doing, or how it gets it done.

At this point I cheated, and looked at the sample code in the problem description, and your system does none of the algorithms.

The first sample algorithm uses naive searching for the median points. Your algorithm does not match that.

The second algorithm uses a reduction-to-size-2 system, and then does a Min/Max formula to get the final result. You do not do this either.

The final algorithm uses recursion and bifurcation. You do not do recursion.

Bottom line is that you are using an algorithm that is hard to read, not comparable to reference systems, and, in the long run, is not much fun to review.

Since I do these reviews for my (twisted) satisfaction as well, I can't say that this one was worth it.

Your opening request is:

I'm looking for code review, clever optimizations, adherence to best practices. etc.

The problem-page you pulled this question from does a perfectly fine job of presenting good code (albeit in C), clever optimizations (that are reproducible in Java quite easily), and the best practices shown there are not great given that it is for C and not Java, but certainly consistent and readable. You have taken those suggestions and ruined them.

Code Review is for reviewing code. I have had to resort to debugging your code just to get a sense of what it does. This is not where code should be when you present it for review.

Answer 3

You could have better testing to ensure your code is correct. I like to verify whether code is correct via code inspection, but sometimes the code is complicated enough that it's difficult to be sure.

You have test cases, which is good, and you add to your test cases when you find a bug: also good.

Two problems with your existing test cases are:

• You have written the input data by hand, yourself; so you test cases only include data which you have thought of. However the code might fail if it is given some data which you haven't thought of.

• You calculate the 'expected result' in your head, and add it to the test case. That makes it difficult to run 100s or 1000s of possible test cases.

Possible solutions:

• If you have a new or tricky implementation, you may be able to test it against a reference implementation. For example when people write a TCP/IP stack, they would test it for interoperability with other, existing, 'known-good' implementations. For this problem, you could either:

  • Choose one the 'reference implementations' from there
  • Write an easy-to-verify implementation: for example, concatenate the two arrays into a third 'target' array, sort the 'target' array, and return the median of the target array: which, you could do in about 3 lines of code, simple enough to verify by inspection.

  Your test suite could then compare output from your code-to-be-tested with the output from your 'known-good' implementation.

• Think about how to get better 'coverage' of your input data; for example:
  • Edge cases (input data which contain 0, or int.MaxValue, or repeating/identical values)
  • Illegal cases (unsorted input, arrays of different lengths) <-- not applicable to this problem
  • Random input (generate the sorted numbers randomly, so that it tests data you haven't even thought of)
  • Complete coverage (test every possible combination of sorted numbers, for arrays of length 2, 3, and 4)

Answer 4

Isn't it much easier to build two merge iterators that walk from beginning and from end? Move them both together. Once their values match or their orders change (a < b => a > b), you calculate the mean between them.

I believe complexity would be O(n+m) and will work even for non-equally sized arrays.

This solution is much simpler for me:

public final class MedianOfTwoSortedArrays {
    private static final class MergeIterator {
        private final double[] a, b;
        private final boolean forward;
        private int i, j;

        public MergeIterator(double[] a, double[] b, boolean forward) {
            this.a = a; this.b = b;
            this.forward = forward;
            if (forward) { i = 0; j = 0; }
            else { i = a.length-1; j = b.length-1; }
        }
        public boolean hasNext() {
            if (forward) return (i < a.length) || (j < b.length);
            else return (i >= 0) || (j >= 0);
        }
        public double next() {
            if (forward) {
                if (j == b.length) return a[i++];
                else if (i == a.length) return b[j++];
                else if (a[i] < b[j]) return a[i++];
                else return b[j++];
            } else {
                if (j < 0) return a[i--];
                else if (i < 0) return b[j--];
                else if (a[i] > b[j]) return a[i--];
                else return b[j--];
            }
        }
    };

    public static double median(double[] a, double[] b)
    {
        MergeIterator i = new MergeIterator(a, b, true);
        MergeIterator j = new MergeIterator(a, b, false);

        while(true)
        {
            double x = i.next(), y = j.next();
            if (x >= y) return (x+y)/2;
        }
    }
};

Tested with:

    double[] a13 = {5, 5, 5, 5};
    double[] a14 = {1, 1, 1, 10};
    // 1, 1, 1, 5,  5, 5, 5, 10
    System.out.println("Expected 5.0, Actual " + median (a13, a14));

Original code gives 7.5 while this gives 5.0.

Updated: fixed MergeIterator for backward walk