CareerCup

Let the two arrays be A1 and A2 and their medians be m1 and m2. Find all elements between m1 and m2 and then find their median.

there are many approaches to do this, see link geeksforgeeks.org/?p=2105

In merge sort there is one function in which we use to merge two sorted array.
Use the same logic here but here we don't have to merge the array only we have to increment two index. Continue the loop uo to (n1+n2)/2 times. Now get the lowest of index1 and index2.

float find_median(int *a, int n1 , int *b , int n2)
{
int n , even_flg = FALSE;
int acount , bcount , ccount;
float median;
acount=0;
bcount=0;
n=(n1+n2)/2;
if((n1+n2)%2==0)
{
even_flg=TRUE;
}

for(ccount=0;ccount<n && acount<n1 && bcount<n2 ; ccount++)
{
if(a[acount]<b[bcount])
{
acount++;
}
else
{
bcount++;
}
}


if(a[acount]<b[bcount])
{
median=(float)a[acount];
}
else
{
median=(float)b[bcount];
}

return median;

}

Also we have to take care
1) array over flow.
2) even number of elements (means n1+n2 is even)
for complete program see
"goursaha.freeoda.com/Miscellaneous/FindMedianFrom2SortedArray.html"

I think this might work as well ::

{ int count =0,number =0, i=0,j=0;
while ( i< A.length && j<B.length ){
count++;
if ( A[i] < B[j] ){
number = A[i];
i++;
}
else{
number = B[j];
j++;
}
if ( count == Math.round((A.length+B.length)/2 ){
return number;
}
}
}

Follow these steps:

Let the arrays be A1 and A2 with start and end as s1,e1 and s2,e2 resp.
1. find the median m1 of A1 and m2 of A2
2. Compare m1 and m2, say m1 < m2 then the median of the two arrays combined should lie in the second half of A1 or the first half of A2.
3. Update s1=m1 and e2=m2. repeat from 1 till you arrive at s1=e1 or s2=e2.

Write code to find kth largest number in the sorted arrays.

if N is odd, find n/2th number using the above algo.
if N is even, find n/2 th number and n/2+1 th number using the above algo. find mean of these two numbers.

Given length of arrays are know, merging two arrays till median is reached will plum it in O(n).

I know a solution which can run in O(logn * log(maxValue-minValue)). Its based on binary search on the range of numbers.

Please check my code

#include<stdio.h>

int findKthsmallest(int a[],int m,int b[],int n,int k)
{
	int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
	while(1)
	{
		ti = (int)((double)m/(m+n) * (k-1));
		tj = (k-1)-ti;
		i = I+ti;
		j= J+tj;
		//printf(" i=%d j=%d\n",i,j);
		if(j>0 && j<N && i<M && a[i]>b[j-1] && a[i]<b[j])
			return a[i];
		if(i>0 && i<M && j<N && b[j]>a[i-1] && b[j]<a[i])
			return b[j];
		if(j==0 && i<M && a[i]<b[j])
			return a[i];
		if(i==0 && j<N && b[j]<a[i])
			return b[j];
		if(j==N && a[i]>b[j-1])
			return a[i];
		if(i==M && b[j]>a[i-1])
			return b[j];
		if(i<M && j<N)
		{
			if(a[i]<b[j])
			{
				k=k-ti-1;
				m=m-ti-1;
				I=i+1;
			}
			else
			{
				k=k-tj-1;
				n=n-tj-1;
				J=j+1;
			}
		}
		else if(i>=M)
		{
			k=k-tj-1;
			n=n-tj-1;
			J=j+1;
		}
		else
		{
			k=k-ti-1;
			m=m-ti-1;
			I=i+1;
		}
	}
}

int main()
{
	int a[]={1,2,3};
	int b[]={4};
	int m=3,n=1,k=3;
	printf("%d",findKthsmallest(a,m,b,n,k));
	return 0;
}

Feedbacks are welcome

int FindKthSmallest(int *a, int an, int *b, int bn, int k)
{
if (an == 0) return b[k];
if (bn == 0) return a[k];

int mida = an/2;
int midb = bn/2;

if (a[mida] == b[midb])
{
if (k == mida + midb)
{
return a[mida];
}
else if (k < mida + midb)
{
return FindKthSmallest(a, mida, b, midb, k);
}
else
{
FindKthSmallest(a+mida, an - mida, b+midb, bn - midb, k - mida - midb);
}
}
}

2 pointer， 1 quick pointer（everytime jump 2 steps）， 1 slower pointer（1 step per jump），

My solution in C++. The running time should be O(log(max - min) * log(totalSize)) using double dichotomy (see comments). It seems to be working :)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/*  Count the number of items in L with value <= L
    L is sorted, so we do it in logarithmic time.
*/
int countInf(vector<int> L, int m) {
    int cnt = 0, i;
    while (cnt < L.size() && L[cnt] <= m) {
        for (i = 1; cnt + (i << 1) < L.size() && L[cnt + (i << 1)] <= m; i <<=1) {}
        cnt += i;
    }
    return cnt;
}

/*
    We now find the median value by dichotomy starting between the min and max value.
    We do O(log(max - min)) round of the loop, each of them calling countInf on both list.
    The running time is O(log(max - min) * log(total size))
*/
#define countTotalInf(m)    (countInf(L1, m) + countInf(L2, m))
int findMedian(vector<int> L1, vector<int> L2) {
    if (L1.size() == 0)
        return (L2.size() == 0) ? 0 : L2[L2.size() / 2];
    if (L2.size() == 0)
        return L1[L2.size() / 2];

    int middle, start = min(L1[0], L2[0]), end = max(L1[L1.size() - 1], L2[L2.size() - 1]);

    while (start != end) {
        middle = (start + end) / 2;
        if (countTotalInf(middle) < (L1.size() + L2.size()) / 2)
            start = middle + 1;
        else
            end = middle;
    }
    return start;
}

int main(int argc, char* argv[]) {
    int ar1[] = {1, 3, 5, 9, 23, 42};
    int ar2[] = {2, 7, 10, 13, 26, 52, 73};
    vector<int> L1(ar1, ar1 + sizeof(ar1) / sizeof(int));
    vector<int> L2(ar2, ar2 + sizeof(ar2) / sizeof(int));
    cout << findMedian(L1, L2) << endl;     // Prints 9
    return 0;
}

Here's my compact implementation of O(log(m+n)) time algorithm. It is based on the findKth with the complexity of O(log(min(k,m,n))). O(1) space.

Please note that O(log(m+n)) is better than previously proposed O(log(m)+log(n)) since latter equals to O(log(nm))

int findKth(int A[], int m, int B[], int n, int k)
	{
		assert(k < m + n && k >= 0);
		if (m == 0) return B[k];
		if (n == 0) return A[k];
		if (k == 0) return min(A[0], B[0]);
		int halfK = (k + 1) / 2;
		int asub, bsub;
		asub = min(halfK, m);
		bsub = min(halfK, n);
		if (A[asub - 1] < B[bsub - 1])
			return findKth(A + asub, m - asub, B, n, k - asub);
		else return findKth(A, m, B + bsub, n - bsub, k - bsub);
	}

	double findMedianSortedArrays(int A[], int m, int B[], int n) {
		if (m + n == 0) return INT_MIN;
		int k = (m + n) / 2;
		double result = findKth(A, m, B, n, k);
		if ((m + n) % 2 == 0)
			result = (result + findKth(A, m, B, n, k - 1)) / 2;
		return result;
	}

For finding the median of two sorted arrays we will have to so the binary search on the smaller array and then, we need to handle some of the corner test cases such as when the index of the first array is 0 that is it's left part is empty then the next element of the second array becomes the median and also when the index of the first array comes to be equal to its size than, we will return the sum of median along with the next element of the first array and similarly with the second array.

Implementation:

int findmedian(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 = ((m + n + 1) / 2) - i;
		 if(i < n && j > 0 && 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(b[j], a[i])) / 2.0;
}