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));        }}
Median of two sorted equal sized arrays on combination
java;array;binary search
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 - iThat'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.5Expected 6.5, Actual 6.5Expected 4.5, Actual 4.5Expected 4.5, Actual 4.5Expected 5.0, Actual 5.0Expected 5.0, Actual 5.0Expected 5.0, Actual 5.0