Median of two sorted equal sized arrays on combination 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] &gt;= a2[pos]) &amp;&amp; (a1[pos] &lt;= a2[pos + 1]);
    }


    private static double calculateMedian(int[] a1, int a1median, int[] a2, int a2median) {
        if (a1median == 0 || a2median == 0 || a1[a2median] &lt; 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 &lt;= 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] &lt; a2[a2Median]) {
                lb = a1Median + 1;
            }

            if (a1[a1Median] &gt; 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));    
    }
}
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.


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.
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.