There are two sorted arrays
arr1[]
and
arr2[]
of size
n
each, write a program to find the
median of the two sorted arrays.
Problem Note
-
You have to find the median of the array formed by merging both the arrays (i.e. array of length
2*n
). -
The overall run time complexity should be
O(log n)
. -
You may assume
arr1[]
andarr2[]
cannot be empty.
Example 1
Input:
arr1[] = [1, 14, 15, 24, 35]
arr2[] = [2, 13, 19, 32, 47]
Output: 17
Explanation: After Merging both the array we get [1, 2, 13, 14, 15, 19, 24, 32, 35, 47]. Total number of elements are even, so we need to take average of middle two numbers which is (15+19)/2 = 17.
Example 2
Input:
A[] = [1, 3, 5, 11, 17],
B[] = [9, 10, 11, 13, 14]
Output: 10.5
Explanation: After Merging both the array we get [1, 3, 5, 9, 10, 11, 11, 13, 14, 17]. We need to take average of middle two numbers which is (10+11)/2.