/*Submitted by: Roman Kotoh , ID: 313102576 & Dima Yankovoy , ID: 311868442


Proof for the algorithm for m=n case. Let name middle element as "k"
m1:=median (A, N)    -   O (1)
m2:=median (B, N)    -   O (1)
Proof:
If m1 < m2, so m1 < k < m2 otherwise m2 < k < m1
Without loss of generality –if  m1 < k < m2, we know that the median of the two arrays must be
Must be A[m1] < k <B [m2] so we can drop the irrelevant parts (A[0….m1] , B[m2……N]) by searching for new medians in each array.

Proof by contradiction:
Again without loss of generality…
We will assume that k is found within ((A[0….m1] U B[m2……N]))
Array A contains (((N+1)/2) -1) elements smaller than m1
Array B contains maximum (((N+1)/2) -1) elements smaller than m2
Unified set is -  ((A[0….m1] U B[m2……N]))   :
(((N+1)/2) -1) + (((N+1)/2) -1) = N-1  <- elements before m1
Contradicting the definition of median which is N= [((2N+1) / 2)]
We can come to a conclusion that k cannot be a part of  ((A[0….m1] U B[m2……N]))
Therefore it must be found somewhere  ((A[m1….n] U B[0….m2]))

m1:=median (A+m1, N / 2)    -   O (1)
m2:=median (B, N/ 2)    -   O (1)
By reducing the size of the arrays by half each iteration we logarithmically decreasing the running time and thus improving efficiency – O (logN)
And we repeat until size = 1 or 2


Efficiency :

T(N) = T(N/2) + 1
T(1) = 1
T(N) = T(N/2) + 1 = T(N/4) + 1 + 1 = .......
T(N/(2^k)+k)
N/(2^k) = 1
k = logN  so - > T(N) = logN + 1

We can sum the efficiency of the algorithm to O (logN)


*/

#include<stdio.h>

int max(int x, int y); /* maximum of two integers */
int min(int x, int y); /* minimum of two integeres */
int median_of_array(int arr[], int n); /*median of a sorted array */
int median_of_2_sorted_arrays_iterative(int ar1[], int ar2[], int n); /*returns median of ar1[] and ar2[]*/


/* main for test */
void main()
{
	int ar1[] = { 1, 2, 3, 5, 7, 9, 11, 14, 16 };
	int ar2[] = { 6, 8, 10, 12, 13, 18, 19, 27, 33 };
	int n1 = sizeof(ar1) / sizeof(ar1[0]);
	int n2 = sizeof(ar2) / sizeof(ar2[0]);

	if (n1 == n2)
		printf("Median is %d (found iteratively)\n\n", median_of_2_sorted_arrays_iterative(ar1, ar2, n1));
	else
		printf("Doesn't work for arrays of unequal size");


	getchar();

}

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int median_of_2_sorted_arrays_iterative(int ar1[], int ar2[], int n)
{
	int m1; /* For median of ar1 */
	int m2; /* For median of ar2 */
	int * parr1;
	int * parr2;

	/* return -1  for invalid input */
	if (n < 1)
		return -1;
	parr1 = ar1;
	parr2 = ar2;

	while (2 < n)
	{
		m1 = median_of_array(parr1, n); /*median of the first array */
		m2 = median_of_array(parr2, n); /*median of the second array */
		if (m1 == m2)
			return m1;

		if (m1 < m2)
		{
			if (n % 2 == 0)
			{
				parr1 += ((n / 2) - 1);
				n = n - (n / 2) + 1;
			}
			else
			{
				parr1 += (n / 2);
				n -= (n / 2);
			}
		}
		else
		{
			if (n % 2 == 0)
			{
				parr2 += (n / 2 - 1);
				n = n - (n / 2 + 1);
			}
			else
			{
				parr2 += (n / 2);
				n -= (n / 2);
			}
		}
	}

	if (n == 1)
		return (((*parr1) + (*parr2)) / 2);

	if (n == 2)
		return (((max(*parr1, *parr2) + min(*(parr1 + 1), *(parr2 + 1)))) / 2);

}




/* Function to get median of a sorted array */
int median_of_array(int arr[], int n)
{
	if (n % 2 == 0)
		return (arr[n / 2] + arr[n / 2 - 1]) / 2;
	else
		return arr[n / 2];
}


/* maximum func */
int max(int x, int y)
{
	if (x > y)
		return x;
	else
		return y;
}

/* minimum func */
int min(int x, int y)
{
	if (x < y)
		return x;
	else
		return y;
}