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.

• C#
• VB.Net
• C
• C++

									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