Time complexity of finding median of two sorted arrays

Question

I have followed median compare algorithm to find median of two sorted arrays and implemented in java. As per algorithm time complexity is O(lgn) but since it involves creating subarrays(method createSubArr) then I think as per my code it's O(n). Below is code implemented by me.

class Median
{
    public static void main (String[] args)
    {
        int[] a = {1,12,15,26,38,40};
        int[] b = {2,13,17,30,45,50};
        System.out.println(getMedian(a,b,6));
    }

    private static int median(int[] a, int n){
        if(n % 2 == 0) return (a[n/2] + a[(n/2)-1])/2;
        else return a[n/2];
    }
    private static void show(int[] a) {
        for(int i=0;i<a.length;i++) System.out.print(a[i] + " ");
        System.out.println();
    }
    private static int[] createSubArr(int[] a, int start){
        int[] sub = new int[a.length-start];
        for(int i=0;i<a.length-start;i++) sub[i] = a[start+i];
        return sub;
    }
    private static int getMedian(int[] a, int[] b,int n){
        int m1,m2;
        int start=-1;
        int ans = -1;
        if(n<=0) return -1;
        if(n==1) return (a[0] + b[0])/2;
        if(n==2) return (Math.max(a[0],b[0])  + Math.min(a[1],b[1]) )/2;
        m1=median(a,n);
        m2=median(b,n);
        if(m1 < m2) {
            if(n%2==0){
                start = (n/2)-1;
                a = createSubArr(a,start);
            }
            else {
                start = (n/2);
                a = createSubArr(a,(n/2));
            }
        }else{
            if(n%2==0){
                start = (n/2)-1;
                b = createSubArr(b,start);
            }
            else {
                start = (n/2);
                b = createSubArr(b,start);
            }
        }
        return getMedian(a,b,n-start);
    }
}

Thanks.

Answer 1

You can add two extra parameters to getMedian: the start indices of a and b, then there is no need to copy data.

Besides, instead of the snippet:

if (n%2 == 0) {
    x = n/2 - 1;
} else {
    x = n/2;
}

you can simply use (n-1)/2;

You would need to adapt the following two methods to get a O(lg n) algorithm (not tested):

private static int median(int[] a, int a0, int n){
    if(n % 2 == 0) return (a[a0 + n/2] + a[a0 + (n/2)-1])/2;
    else return a[a0 + n/2];
}

private static int getMedian(int[] a, int a0, int[] b, int b0,int n){
    int m1,m2;
    int start=-1;
    int ans = -1;
    if(n<=0) return -1;
    if(n==1) return (a[a0] + b[b0])/2;
    if(n==2) return (Math.max(a[a0],b[b0])  + Math.min(a[a0+1],b[b0+1]) )/2;
    m1=median(a, a0,n);
    m2=median(b, b0,n);
    if(m1 < m2) {
        return getMedian(a, (n-1)/2, b, b0, n - (n-1)/2);
    } else {
        return getMedian(a, a0, b, (n-1)/2, n - (n-1)/2);
    }
}