Median of two sorted Array

Given two sorted arrays array1 and array2 of size m and n respectively. Find the median of the two sorted arrays.

Input Format

The first line contains 2 integers N and M the length of the arrays respectively. The second line contains n integers n1, n2, … the array elements themselves. The third line contains m integers m1, m2, … the array elements themselves.

Output Format

Print the median of the two sorted arrays.

Example 1:

Input:
    3 4
    1 5 9
    2 3 6 7
Output:
    5
Explanation:
    The middle element for {1,2,3,5,6,7,9} is 5

Example 2:

Input:
    2 4
    4 6
    1 2 3 5
Output:
    3.5

Constraints:

• 0 ≤ m,n ≤ 10^4
• 1 ≤ array1[i], array2[i] ≤ 10^5
• Expected Time Complexity: O(min(log n, log m)).
• Expected Auxiliary Space: O((n+m)/2).