There are two sorted arrays A[] and B[] of size n each, write a program to find the median of the two sorted arrays.

Problem Note

  • The median of the array formed by merging both the arrays (i.e. array of length 2n).
  • The overall run time complexity should be O(log n).
  • You may assume A[] and B[] cannot be empty.

Example 1

Input: 
A[] = [1, 12, 15, 26, 38]
B[] = [2, 13, 17, 30, 45] 
Output: 16 
Explanation: After Merging both the array we get [1, 2, 12, 13, 15, 17, 26, 30, 38, 45]. Total number of elements are even, so we need to take average of middle two numbers which is (15+17)/2.

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.