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 Shared Function GetArrayChunk(arr As Integer(), index As Integer) As Integer()
	Dim newLength As Integer = arr.Length - index
	Dim newArray As Integer() = New Integer(newLength - 1) {}
	Array.Copy(arr, index, newArray, 0, newLength)
	Return newArray
End Function

Private Shared Function Median(arr As Integer(), arrSize As Integer) As Integer
	If arrSize Mod 2 = 0 Then
		Return (arr(arrSize \ 2) + arr(arrSize \ 2 - 1)) \ 2
	Else
		Return arr(arrSize \ 2)
	End If
End Function

Public Shared Function GetMedian(arr1 As Integer(), arr2 As Integer(), arrSize As Integer) As Integer
	If arrSize <= 0 Then
		Return -1
	End If
	If arrSize = 1 Then
		Return (arr1(0) + arr2(0)) \ 2
	End If
	If arrSize = 2 Then
		Return (Math.Max(arr1(0), arr2(0)) + Math.Min(arr1(1), arr2(1))) \ 2
	End If

	Dim m1 As Integer = Median(arr1, arrSize)
	Dim m2 As Integer = Median(arr2, arrSize)

	If m1 = m2 Then
		Return m1
	End If

	If m1 < m2 Then
		If arrSize Mod 2 = 0 Then
			Return GetMedian(GetArrayChunk(arr1, arrSize \ 2 - 1), arr2, arrSize - arrSize \ 2 + 1)
		End If
		Return GetMedian(GetArrayChunk(arr1, arrSize \ 2), arr2, arrSize - arrSize \ 2)
	End If

	If arrSize Mod 2 = 0 Then
		Return GetMedian(GetArrayChunk(arr2, arrSize \ 2 - 1), arr1, arrSize - arrSize \ 2 + 1)
	End If

	Return GetMedian(GetArrayChunk(arr2, arrSize \ 2), arr1, arrSize - arrSize \ 2)
End Function
								


Example

									Dim median As Integer = 0
Dim arr1 As Integer() = {1, 2, 3, 6}
Dim arr2 As Integer() = {4, 6, 8, 10}
If arr1.Length = arr2.Length Then
	median = GetMedian(arr1, arr2, arr1.Length)
End If
								


Output

									median: 5