CareerCup

Say you have two lists with n and m elements.

First get a= List1[ceil(n/2)], b= List2[ceil(m/2)]
If a>=b, median must be lesser than a and greater than b..
therefore now consider elements of List1 lesser than a, elements of List2 greater than b
If a<b median must be greater than a and less than b..
therefore now consider elements of List1 greater than a, elements of List2 lesser than b

Continuing this say, in each iteration, you eliminate half of each list.
O(logn) + O(logm) ... if n > m, O(log n) else O(log m)

There is this solution as per the MIT problem set

1st result of Google Search for "median of 2 sorted arrays"

ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

Much better explanation here - geeksforgeeks.org/?p=2105

We can use the merge procedure of the mergesort. We don't need to do the actual merge but just keeping track of the number of elements considered for merge will solve the problem. This is an O(n) time solution.
O(lgn) might be possible through binary search. Thinking about it...

Find median = (len(arr1)+ len(arr2))/2
Place two pointers at the bottom of both the array (arr1_p,arr2_p) .
initialize i=0
pick the move the pointers by this algo
1. compare arr1[arr1_p] with arr2[arr2_p] ...
2. do -1 to the pointer with lesser value and i++
3. if i < median goto 1 else choose the pointer with higher value
OR
in case of even size do (arr1[arr1_p] + arr2[arr2_p])/2

0(n/2)

Most of the algorithms are using the median checks that work only for the arrays of the same length.

For the arrays of different length you must use different approach, the one that is described http://www.drdobbs.com/parallel/finding-the-median-of-two-sorted-arrays/240169222?pgno=2 or in video here https://www.youtube.com/watch?v=_H50Ir-Tves (ignore the (3), there is a mistake because the guy also consider comparing medians to work for different arrays, even though it does not work).

However I think you cannot easily continue recursively in the subarrays as he says in the video, it's safer to just make the range a,b and a2,b2 always smaller instead (but not to forget A.length and B.length values). I don't have a proof though

For finding the median of two sorted arrays we will follow the algorithm given below:

Implementation:

int return_median(int a[], int n, int b[], int m){
	int median, min_index = 0, max_index = n;
	while(min_index <= max_index){
		int i = (min_index + max_index) / 2;
		int j = ((n + m + 1) / 2) - i;
		if(j > 0 && i < n && b[j - 1] > a[i])
			min_index = i + 1;
		else if(i > 0 && j < m && b[j] < a[i - 1])
			max_index = i - 1;
		else{
			if(i == 0)
				median = b[j - 1];
			else if(j == 0)
				median = a[i - 1];
			else
				median = max(a[i - 1], b[j - 1]);
		}
	}
	if((n + m) % 2 == 1)
		return (double)median;
	if(i == n)
		return (median + b[j]) / 2.0;
	if(j == m)
		return (median + a[i]) / 2.0;
	else
		return (median + min(a[i], b[j])) / 2.0;
}

I mentioned the above methods..But I found O(logn) soultion for the same..:-(

I mentioned the above methods..But I found O(logn) soultion for the same..:-(

I mentioned the above methods..But I found O(logn) soultion for the same..:-( on the internet after my interview..