Suppose you are given two sorted arrays A, B of integer values, in increasing or

Question

Suppose you are given two sorted arrays A, B of integer values, in increasing order, sizes n and m respectively, and m+n is an odd value (so we can define the median value uniquely). Develop an algorithm for finding the median of the combined sorted arrays, and analyze the complexity of your algorithm. Hopefully, your worst case complexity will be O(log(m + n)). Implement your algorithm as a Java class to fit the template below.

public class MySolution {
public int findMedianSortedArrays(int A[],int B[]){
// your code goes here, returns the median
}
}

Here is a program to test the above:

public class Solver {

public static void main(String[] args){

       int[] A = {-2,-1, 0,2,3};

       int[] B = {1,4,6,7, 8,9,11,13};

       MySolution sol = new MySolution();

       int answer = sol.findMedianSortedArrays(A,B);

       System.out.println("Answer "+answer)

   }

}

Explanation / Answer

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

public MergeIterator(int[] a, int[] 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 int 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 int median(int[] a, int[] b)
{
MergeIterator i = new MergeIterator(a, b, true);
MergeIterator j = new MergeIterator(a, b, false);

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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.