CareerCup

double findKth(int A[], int m, int B[], int n, int k) {

    if (m > n) return findKth(B, n, A, m, k);
    if (m == 0) return B[k - 1];
    if (k == 1) return min(A[0], B[0]);

    int aMid = min(k / 2, m);
    int bMid = k - aMid;

    if (A[aMid - 1] <= B[bMid - 1]) {
        return findKth(A + aMid, m - aMid, B, n, k - aMid);
    }
    return findKth(A, m, B + bMid, n - bMid, k - bMid);
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m + n;
    if(total & 1) return findKth(A, m, B, n, total / 2 + 1);
    return (findKth(A, m, B, n, total / 2);
}

The overall time complexity is

O(log(n + n))

which is

O(logn)

.

- Kaidul Islam October 14, 2014 | Flag Reply

public static int findLowerMedian(int[] a, int[]b){
        int atry, btry;
        atry = findLowerMedianIndex(a, b, 0, a.length);
        if(atry != -1){
            return a[atry];
        }
        else{
            return b[findLowerMedianIndex(b, a, 0, b.length)];
        }
    }

    public static int findLowerMedianIndex(int[] a, int[] b, int start, int end){
        if(start == end){
            if(lowerMedianProximity(a, b, start) == 0) return start;
            else return -1;
        }
        else{
            int m = (start + end)/2;
            int prox = lowerMedianProximity(a, b, m);
            if(prox == 0) return m;
            else if(prox == -1) return findLowerMedianIndex(a, b, m+1, end);
            else return findLowerMedianIndex(a, b, start, m);
        }
    }


    public static int lowerMedianProximity(int[] a, int[] b, int adex){
        int firstGreater = a.length - 1 - adex;
        if(b[firstGreater] > a[adex] && b[firstGreater-1] < a[adex]) return 0;
        else if(b[firstGreater] > a[adex]) return -1;
        else return 1;
    }

- Anonymous October 14, 2014 | Flag Reply

int get( const vector< int >  &a, int lo, int hi, const int e ) {
	int ret = lo;
	while( lo <= hi ) {
		int mid = ( lo + hi ) / 2;
		if( a[mid] > e ) hi = mid - 1;
		else {
			lo = mid + 1;
			if( ret < mid ) ret = mid;
		}
	}
	return ret;
}

int lowerMedian ( const vector<int> S, const vector<int> T) {

	int N = S.size();
	int M = T.size();

	int i = 0 , j = 0 ;

	int needSmaller = N+M;

	if( !needSmaller ) return -1; /// Both vectors are empty

	if( needSmaller % 2 ) needSmaller /= 2;
	else needSmaller = ( needSmaller / 2 ) - 1;

	while( i < N || j < M ) {

		if( i == N ) return T[j + needSmaller];
		if( j == M ) return S[ i + needSmaller ];

		if( S[i] < T[j] ) {
			if( !needSmaller ) return S[i];
			int idx = get ( S , i , N-1 , T[j] );
			if( idx - i >= needSmaller ) return S[ i + needSmaller ] ;
			needSmaller -= idx - i + 1;
			i = idx + 1;
			continue;
		}

		if( S[i] > T[j] ) {
			if( !needSmaller ) return T[j];
			int idx = get ( T , j , M-1 , S[i] );
			if( idx - j >= needSmaller ) return T[ j + needSmaller ];
			needSmaller -= idx - j + 1;
			j = idx + 1;
			continue;
		}
	}
	
	/// code will not come here
	return -1;
}

- Bidhan Roy October 15, 2014 | Flag Reply

GeeksForGeeks

Perfect O(log(n))

public class GetMedianRec {

/*
* This function returns median of ar1[] and ar2[]. Assumptions in this
* function: Both ar1[] and ar2[] are sorted arrays Both have n elements
*/
static int getMedian(int ar1[], int ar2[], int n) {
return getMedianRec(ar1, ar2, 0, n - 1, n);
}

/*
* A recursive function to get the median of ar1[] and ar2[] using binary
* search
*/
static int getMedianRec(int ar1[], int ar2[], int left, int right, int n) {
int i, j;

/* We have reached at the end (left or right) of ar1[] */
if (left > right)
return getMedianRec(ar2, ar1, 0, n - 1, n);

i = ((left + right) / 2);

j = n - i - 1; /* Index of ar2[] */

/* Recursion terminates here. */
if (ar1[i] > ar2[j] && (j == n - 1 || ar1[i] <= ar2[j + 1])) {
/*
* ar1[i] is decided as median 2, now select the median 1 (element
* just before ar1[i] in merged array) to get the average of both
*/
if (i == 0 || ar2[j] > ar1[i - 1])
return Math.min(ar1[i], ar2[j]);
else
return Math.min(ar1[i], ar1[i - 1]);
}

/* Search in left half of ar1[] */
else if (ar1[i] > ar2[j] && j != n - 1 && ar1[i] > ar2[j + 1])
return getMedianRec(ar1, ar2, left, i - 1, n);

/* Search in right half of ar1[] */
else
/* ar1[i] is smaller than both ar2[j] and ar2[j+1] */
return getMedianRec(ar1, ar2, i + 1, right, n);
}

public static void main(String[] args) {
int ar1[] = { 1, 2 };
int ar2[] = { 4, -2 };

System.out.println(getMedian(ar1, ar2, ar1.length));
}
}

- inevitablekris October 15, 2014 | Flag Reply

{{{ merge :: [Int] -> [Int] -> [Int] merge [] (x:xs) = [x] ++ xs merge (x:xs) [] = [x] ++ xs merge (x:xs) (y:ys) | x > y = [y] ++ merge ([x] ++ xs) ys | otherwise = [x] ++ merge xs ([y] ++ ys) }}} {{{ let t = merge [3,6,7,9] [-1,1,2,8] *Main> t !! ((length t) `div` 2 - 1) 3 } - Anonymous October 21, 2014 | Flag Reply

{{{ merge :: [Int] -> [Int] -> [Int] merge [] (x:xs) = [x] ++ xs merge (x:xs) [] = [x] ++ xs merge (x:xs) (y:ys) | x > y = [y] ++ merge ([x] ++ xs) ys | otherwise = [x] ++ merge xs ([y] ++ ys) }}} {{{ let t = merge [3,6,7,9] [-1,1,2,8] *Main> t !! ((length t) `div` 2 - 1) 3 } - AD October 21, 2014 | Flag Reply

Reformatted :

merge :: [Int] -> [Int] -> [Int] 
merge [] (x:xs) = [x] ++ xs 
merge (x:xs) [] = [x] ++ xs 
merge (x:xs) (y:ys)
  | x > y = [y] ++ merge ([x] ++ xs) ys
  | otherwise = [x] ++ merge xs ([y] ++ ys)

- AD October 21, 2014 | Flag Reply

let t = merge [3,6,7,9] [-1,1,2,8] 
t !! ((length t) `div` 2 - 1)

- AD October 21, 2014 | Flag Reply