Median Of Two Sorted Arrays

This algorithm finds the median of two sorted arrays by first getting medians of the two sorted arrays and then comparing them.



									private static int[] GetArrayChunk(int[] arr, int index)
{
	int newLength = arr.Length - index;
	int[] newArray = new int[newLength];
	Array.Copy(arr, index, newArray, 0, newLength);
	return newArray;
}

private static int Median(int[] arr, int arrSize)
{
	if (arrSize % 2 == 0) return (arr[arrSize / 2] + arr[arrSize / 2 - 1]) / 2;
	else return arr[arrSize / 2];
}

public static int GetMedian(int[] arr1, int[] arr2, int arrSize)
{
	if (arrSize <= 0) return -1;
	if (arrSize == 1) return (arr1[0] + arr2[0]) / 2;
	if (arrSize == 2) return (Math.Max(arr1[0], arr2[0]) + Math.Min(arr1[1], arr2[1])) / 2;

	int m1 = Median(arr1, arrSize);
	int m2 = Median(arr2, arrSize);

	if (m1 == m2) return m1;

	if (m1 < m2)
	{
		if (arrSize % 2 == 0) return GetMedian(GetArrayChunk(arr1, arrSize / 2 - 1), arr2, arrSize - arrSize / 2 + 1);
		return GetMedian(GetArrayChunk(arr1, arrSize / 2), arr2, arrSize - arrSize / 2);
	}

	if (arrSize % 2 == 0) return GetMedian(GetArrayChunk(arr2, arrSize / 2 - 1), arr1, arrSize - arrSize / 2 + 1);

	return GetMedian(GetArrayChunk(arr2, arrSize / 2), arr1, arrSize - arrSize / 2);
}
								


Example

									int median = 0;
int[] arr1 = { 1, 2, 3, 6 };
int[] arr2 = { 4, 6, 8, 10 };
if (arr1.Length == arr2.Length)
	median = GetMedian(arr1, arr2, arr1.Length);
								


Output

									median: 5